Алгоритми та структури даних · Senior · Запитання 66 з 75
У чому головна перевага Дейкстри з купою Фібоначчі над бінарною купою?
- ✓Правильна відповідь: Амортизований decrease-key за O(1): O(E + V log V)
- 2Йому взагалі не потрібна черга з пріоритетом
- 3Він також коректно працює з від'ємними вагами
Пояснення
На щільних графах це краще за O((V + E) log V). На практиці бінарні купи (часто з лінивим видаленням замість decrease-key) зазвичай швидші, бо купи Фібоначчі мають великі константи.