Algorytmy i struktury danych · Senior · Pytanie 42 z 75
Dlaczego wyszukiwanie binarne nie działa wydajnie na liście wiązanej?
- 1List wiązanych nie da się trzymać posortowanych
- ✓Poprawna odpowiedź: Dojście do środka kosztuje O(n), bo nie ma dostępu swobodnego
- 3Wyszukiwanie binarne potrzebuje długości, a listy jej nie mają
Wyjaśnienie
Wyszukiwanie binarne opiera się na dostępie po indeksie w O(1). Na liście każdy krok dzielenia przechodzi połowę pozostałych węzłów, więc razem O(n). Skip list dodaje wskaźniki, aby przywrócić O(log n).