Algorytmy i struktury danych · Middle · Pytanie 73 z 75
Ile kosztuje wstawienie wartości do posortowanej tablicy z zachowaniem porządku?
- ✓Poprawna odpowiedź: O(n): miejsce znajdujemy w O(log n), ale przesunięcie elementów to O(n)
- 2O(1): tablice JavaScriptu wstawiają wszędzie za darmo
- 3O(log n): wyszukiwanie binarne od razu znajduje pozycję
Wyjaśnienie
Wyszukiwanie binarne szybko znajduje pozycję, ale splice i tak przesuwa każdy kolejny element. Przy wielu wstawieniach z wyszukiwaniami pomiędzy lepiej pasuje zbalansowane drzewo lub kopiec (zależnie od zapytań).