Алгоритми та структури даних · Middle · Запитання 73 з 75
Скільки коштує вставити значення у відсортований масив, зберігши порядок?
- ✓Правильна відповідь: O(n): місце знаходимо за O(log n), але зсув елементів - O(n)
- 2O(1): масиви JavaScript безкоштовно вставляють будь-де
- 3O(log n): бінарний пошук одразу знаходить позицію
Пояснення
Бінарний пошук швидко знаходить позицію, але splice усе одно зсуває кожен наступний елемент. Для багатьох вставок із пошуками між ними краще підходить збалансоване дерево або купа (залежно від запитів).