Algorytmy i struktury danych · Senior · Pytanie 66 z 75
Jaka jest główna przewaga Dijkstry z kopcem Fibonacciego nad kopcem binarnym?
- ✓Poprawna odpowiedź: Zamortyzowane decrease-key w O(1): O(E + V log V)
- 2W ogóle nie potrzebuje kolejki priorytetowej
- 3Działa też poprawnie z ujemnymi wagami
Wyjaśnienie
Na gęstych grafach to lepsze niż O((V + E) log V). W praktyce kopce binarne (często z leniwym usuwaniem zamiast decrease-key) są zwykle szybsze, bo kopce Fibonacciego mają duże stałe.