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

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

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).

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

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.

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.

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)

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).

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)

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).