Zrozumienie Obliczanie złożoności czasu dla algorytmu Dijkstra

Question

Zgodnie z moim rozumowaniem, obliczyłem złożoność czasową algorytmu Dijkstra jako notacji big-o, używając poniższej listy rozgraniczenia. Nie wyszło tak, jak powinno, i to doprowadziło mnie do zrozumienia go krok po kroku.

1. Każdy wierzchołek może być połączony z wierzchołkami (V-1), a więc liczba przylegających krawędzi dla każdego wierzchołka wynosi V - 1. Załóżmy, E oznacza V-1 krawędzie połączone z każdym wierzchołku.
2. Wyszukiwanie & Aktualizowanie masy każdego sąsiedniego wierzchołka w sterty min wynosi O (log (V)) + O (1) lub O(log(V)).
3. W związku z tym, od kroku 1 i kroku 2 powyżej, złożoność czasowa dla aktualizacji wszystkich sąsiednich wierzchołków wierzchołka to E * (logV). lub E*logV.
4. Stąd złożoność czasowa dla wszystkich wierzchołków V wynosi V * (E * logV), tj. O(VElogV).

Ale złożoność czasowa dla algorytmu Dijkstra to O (ElogV). Czemu?

Answer 1

najkrótsza algorytm ścieżka Dijkstry jest O(ElogV) gdzie:

• V jest liczbą wierzchołków
• E to łączna liczba krawędzi

Twoja analiza jest poprawna, ale twoje symbole mają różne znaczenia! Mówisz, że algorytm jest O(VElogV) gdzie:

• V jest liczbą wierzchołków
• E jest maksymalna liczba krawędzi przyłączonych do jednego węzła.

Zmieńmy nazwę użytkownika na E na N. Tak więc jedna analiza mówi: O(ElogV), a druga mówi: O(VNlogV). Oba są poprawne i faktycznie E = O(VN). Różnica polega na tym, że ElogV jest dokładniejszym oszacowaniem.