Złożoności algorytmu Dijkstry

0

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

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.

1 użytkowników online, w tym zalogowanych: 0, gości: 1