Dlaczego złożoność czasowa zarówno DFS, jak i BFS O (V + E)

137

Podstawowy algorytm dla BFS:

set start vertex to visited

load it into queue

while queue not empty

   for each edge incident to vertex

        if its not visited

            load into queue

            mark vertex

Więc myślę, że złożoność czasowa byłaby następująca:

v1 + (incident edges) + v2 + (incident edges) + .... + vn + (incident edges) 

gdzie vjest wierzchołek 1nan

Po pierwsze, czy to, co powiedziałem, jest prawidłowe? Po drugie, jak to jest O(N + E)i intuicja, dlaczego byłoby naprawdę fajnie. Dzięki

zwyczajny
źródło

Odpowiedzi:

276

Twoja suma

v1 + (incident edges) + v2 + (incident edges) + .... + vn + (incident edges)

można przepisać jako

(v1 + v2 + ... + vn) + [(incident_edges v1) + (incident_edges v2) + ... + (incident_edges vn)]

a pierwsza grupa jest, O(N)podczas gdy druga jest O(E).

Mihai Maruseac
źródło
1
Ale każdy wierzchołek musi zostać wyodrębniony z kolejki, a to jest log (| Q |) A co z tą częścią?
Yola,
3
log (| Q |) <log (N) <N stąd możesz spokojnie zignorować termin w
asymptozie
2
Jeśli na liście przylegania każdy wierzchołek jest połączony ze wszystkimi innymi wierzchołkami, złożoność byłaby równoważna O (V + E) = O (V + V ^ 2) = O (V ^ 2). E = V ^ 2, ponieważ największa liczba krawędzi = V ^ 2.
Max
Zgodnie z twoją odpowiedzią, czy złożoność nie zmieni się na O (V + 2E)? Ponieważ każda krawędź może mieć wspólną krawędź z inną?
karansky
2
Stałe warunki można porzucić.
Mihai Maruseac
41

DFS (analiza):

  • Ustawienie / pobranie etykiety wierzchołka / krawędzi wymaga O(1)czasu
  • Każdy wierzchołek jest dwukrotnie oznaczony
    • raz jako UNEXPLORED
    • raz, jak odwiedziłem
  • Każda krawędź jest dwukrotnie opisana
    • raz jako UNEXPLORED
    • raz jako DISCOVERY lub BACK
  • Metoda incidentEdges jest wywoływana raz dla każdego wierzchołka
  • DFS działa w O(n + m)czasie, pod warunkiem, że wykres jest reprezentowany przez strukturę listy sąsiedztwa
  • Odwołaj to Σv deg(v) = 2m

BFS (analiza):

  • Ustawienie / pobranie etykiety wierzchołka / krawędzi zajmuje O (1) czasu
  • Każdy wierzchołek jest dwukrotnie oznaczony
    • raz jako UNEXPLORED
    • raz, jak odwiedziłem
  • Każda krawędź jest dwukrotnie opisana
    • raz jako UNEXPLORED
    • raz jako DISCOVERY lub CROSS
  • Każdy wierzchołek jest wstawiany raz w sekwencję Li
  • Metoda incidentEdges jest wywoływana raz dla każdego wierzchołka
  • BFS działa w O(n + m)czasie pod warunkiem, że wykres jest reprezentowany przez strukturę listy sąsiedztwa
  • Odwołaj to Σv deg(v) = 2m
Nowy
źródło
tnx do edycji Jestem tu nowy, więc nadal próbuję sobie poradzić z ekranem edycji :)
TheNewOne
1
dziękuję za dokładność, wspominając, że wykresy mają być reprezentowane przez strukturę listy sąsiedztwa, wkurzało mnie, dlaczego DFS jest O (n + m), myślę, że to było O (n + 2m), ponieważ każda krawędź jest przechodzona dwukrotnie cofając się.
mib1413456
23

Bardzo uproszczone bez większych formalności: każda krawędź jest rozpatrywana dokładnie dwa razy, a każdy węzeł jest przetwarzany dokładnie raz, więc złożoność musi być stałą wielokrotnością liczby krawędzi i liczby wierzchołków.

Neetesh Dadwariya
źródło
O wiele łatwiejszy do zrozumienia niż notacja matematyczna bez dalszych wyjaśnień, chociaż po to jest Google.
mLstudent33
dlaczego każda krawędź jest brana pod uwagę dokładnie dwa razy?
amy
Każdy wierzchołek jest odwiedzany co najwyżej jeden raz, ponieważ tylko pierwszy raz, gdy zostanie osiągnięty, jest równy zeru, a więc każdy wierzchołek jest kolejkowany najwyżej raz. Ponieważ badamy krawędzie padające na wierzchołek tylko wtedy, gdy odwiedzamy go z niego, każda krawędź jest badana najwyżej dwa razy, raz dla każdego wierzchołka, na którym się pojawia. Zobacz źródło
Neetesh Dadwariya
11

Złożoność czasowa jest O(E+V)zamiast tego, O(2E+V)ponieważ jeśli złożoność czasowa wynosi n ^ 2 + 2n + 7, to jest zapisywana jako O (n ^ 2).

Stąd O (2E + V) jest zapisane jako O (E + V)

ponieważ różnica między n ^ 2 a n ma znaczenie, ale nie ma znaczenia między n a 2n.

Dhruvam Gupta
źródło
@Am_I_Pomocne ktoś pyta powyżej o 2E w notacji duże-och .... dlatego 2 nie jest brane pod uwagę w złożoności czasowej.
Dhruvam Gupta
@Am_I_Pomocne, zobacz post nad moją odpowiedzią .... tam użytkownik o imieniu Kehe CAI napisał: „Myślę, że każda krawędź była brana pod uwagę dwa razy i każdy węzeł był odwiedzany raz, więc łączna złożoność czasu powinna wynosić O (2E + V ). ” Więc odpowiedziałem zgodnie .... Rozumiem !!!
Dhruvam Gupta
Usunąłem mój głos przeciwny tylko dlatego, że zredagowałeś swoją odpowiedź,
Am_I_Helpful
5

Intuicyjnym wyjaśnieniem tego jest po prostu analiza pojedynczej pętli:

  1. odwiedzić wierzchołek -> O (1)
  2. a pętla for na wszystkich krawędziach padających -> O (e) gdzie e jest liczbą krawędzi padających na dany wierzchołek v.

Zatem całkowity czas dla pojedynczej pętli wynosi O (1) + O (e). Teraz zsumuj to dla każdego wierzchołka, ponieważ każdy wierzchołek jest odwiedzany raz. To daje

For every V
=> 

    O(1)
    +

    O(e)

=> O(V) + O(E)
Ultrablendz
źródło
3

Myślę, że każda krawędź była rozważana dwukrotnie i każdy węzeł był odwiedzany raz, więc całkowita złożoność czasowa powinna wynosić O (2E + V).

Kehe CAI
źródło
Nawet ja czuję to samo. Czy ktoś może udzielić dalszych wyjaśnień w tej sprawie?
Chaitanya
12
Analiza Big O ignoruje stałą. O (2E + V) jest O (E + V).
Hemm
3

Krótkie, ale proste wyjaśnienie:

W najgorszym przypadku musiałbyś odwiedzić wszystkie wierzchołki i krawędzie, stąd złożoność czasowa w najgorszym przypadku to O (V + E)

CodeYogi
źródło
0

Jest to O (V + E), ponieważ każda wizyta w v z V musi odwiedzić każde e z E, gdzie | e | <= V-1. Ponieważ jest V wizyt na v z V, to jest to O (V). Teraz musisz dodać V * | e | = E => O (E). Zatem całkowita złożoność czasowa wynosi O (V + E).

awgtek
źródło