Pesymistyczna złożoność algorytmu Dijskry dla kolejki opisanej na tablicy wynosi O(V^2), kto mi powie jaka jest optymistyczna żłożoność, oraz czy algorytm jest wrażliwy na dane oraz czy działa w miejscu?
0
0
Dawno nie zajmowałem się Dijkstrą, ale może dobrze pamiętam:
- Nie działa w miejscu, oczywiście, bo trzeba pamięć na kolejkę,
- Optymistyczna złożoność to O(V) = O(E) w przypadku, gdy badany graf jest ścieżką,
- Jest wrażliwy na dane, złożoność jest proporcjonalna do sumy kwadratów ilości wychodzących ścieżek z każdego wierzchołka, a więc inaczej rozstawione połączenia mogą zmienić złożoność,
0
Dziękuje :) rzeczywiście to ma sens.