Warum ist die zeitliche Komplexität von DFS und BFS O (V + E)

132

Der grundlegende Algorithmus für 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

Ich würde also denken, die zeitliche Komplexität wäre: 

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

wo vist Vertex 1zun

Ist das, was ich gesagt habe, richtig? Zweitens, wie ist das O(N + E)und die Intuition, warum das so schön wäre. Vielen Dank

algorithm time-complexity graph-theory breadth-first-search gewöhnliche
quelle

Antworten:

268

Deine Summe

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

kann umgeschrieben werden als

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

und die erste Gruppe ist, O(N)während die andere ist O(E).

Mihai Maruseac
quelle
1
Aber jeder Scheitelpunkt muss aus der Warteschlange extrahiert werden, und dies ist log (| Q |). Was ist mit diesem Teil?
Yola
3
log (| Q |) <log (N) <N daher können Sie den Begriff in der asymptotischen
Mihai Maruseac
2
Wenn in einer Adjazenzliste jeder Scheitelpunkt mit allen anderen Scheitelpunkten verbunden ist, wäre die Komplexität äquivalent zu O (V + E) = O (V + V ^ 2) = O (V ^ 2). E = V ^ 2, weil die meisten Kanten = V ^ 2 sind.
Max
Wird die Komplexität Ihrer Antwort zufolge nicht zu O (V + 2E)? Da jede Kante eine gemeinsame Kante mit einer anderen Kante haben könnte?
Karansky
2
Die konstanten Terme können gelöscht werden.
Mihai Maruseac
41

DFS (Analyse):

  • Das Festlegen / Abrufen einer Scheitelpunkt- / Kantenbeschriftung dauert einige O(1)Zeit
  • Jeder Scheitelpunkt ist zweimal beschriftet
    • einmal als UNEXPLORED
    • einmal als BESUCHT
  • Jede Kante ist zweimal beschriftet
    • einmal als UNEXPLORED
    • einmal als ENTDECKUNG oder ZURÜCK
  • Die Methode IncidentEdges wird für jeden Scheitelpunkt einmal aufgerufen
  • DFS wird O(n + m)rechtzeitig ausgeführt, sofern das Diagramm durch die Adjazenzlistenstruktur dargestellt wird
  • Erinnere dich daran Σv deg(v) = 2m

BFS (Analyse):

  • Das Festlegen / Abrufen einer Scheitelpunkt- / Kantenbeschriftung dauert O (1)
  • Jeder Scheitelpunkt ist zweimal beschriftet
    • einmal als UNEXPLORED
    • einmal als BESUCHT
  • Jede Kante ist zweimal beschriftet
    • einmal als UNEXPLORED
    • einmal als ENTDECKUNG oder KREUZ
  • Jeder Scheitelpunkt wird einmal in eine Sequenz eingefügt Li
  • Die Methode IncidentEdges wird für jeden Scheitelpunkt einmal aufgerufen
  • BFS wird O(n + m)rechtzeitig ausgeführt, sofern das Diagramm durch die Adjazenzlistenstruktur dargestellt wird
  • Erinnere dich daran Σv deg(v) = 2m
TheNewOne
quelle
tnx für die Bearbeitung Ich bin neu hier, also versuche ich immer noch mit dem Bearbeitungsbildschirm zu verwalten :)
TheNewOne
1
Vielen Dank, dass Sie spezifisch erwähnt haben, dass die Diagramme durch die Struktur der Adjazenzliste dargestellt werden sollen. Es hat mich gestört, warum DFS O (n + m) ist. Ich würde denken, es war O (n + 2 m), da jede Kante zweimal durchlaufen wird durch Zurückverfolgen.
mib1413456
22

Sehr vereinfacht ohne viel Formalität: Jede Kante wird genau zweimal betrachtet und jeder Knoten wird genau einmal verarbeitet, daher muss die Komplexität ein konstantes Vielfaches der Anzahl der Kanten sowie der Anzahl der Eckpunkte sein.

Neetesh Dadwariya
quelle
Viel einfacher zu verstehen als die mathematische Notation ohne weitere Erklärung, obwohl Google dafür gedacht ist.
mLstudent33
11

Zeitkomplexität ist O(E+V)statt O(2E+V)weil, wenn die Zeitkomplexität n ^ 2 + 2n + 7 ist, dann wird sie als O (n ^ 2) geschrieben.

Daher wird O (2E + V) als O (E + V) geschrieben.

weil der Unterschied zwischen n ^ 2 und n wichtig ist, aber nicht zwischen n und 2n.

Dhruvam Gupta
quelle
@Am_I_Helpful jemand fragt oben nach 2E in Big-Oh-Notation .... deshalb wird 2 in der Zeitkomplexität nicht berücksichtigt.
Dhruvam Gupta
@Am_I_Helpful siehe nur den Beitrag über meiner Antwort ... dort hat der Benutzer namens Kehe CAI geschrieben: "Ich denke, jede Kante wurde zweimal berücksichtigt und jeder Knoten wurde einmal besucht, daher sollte die Gesamtzeitkomplexität O (2E + V sein ). " Also antwortete ich entsprechend .... Verstanden !!!
Dhruvam Gupta
Ich habe meine Ablehnung nur entfernt, weil Sie Ihre Antwort bearbeitet haben
Am_I_Helpful
3

Ich denke, jede Kante wurde zweimal berücksichtigt und jeder Knoten wurde einmal besucht, daher sollte die Gesamtzeitkomplexität O (2E + V) sein.

Kehe CAI
quelle
Sogar mir geht es genauso. Kann jemand weitere Erklärungen dazu geben?
Chaitanya
12
Die Big O-Analyse ignoriert die Konstante. O (2E + V) ist O (E + V).
Hemm
3

Eine intuitive Erklärung hierfür ist die einfache Analyse einer einzelnen Schleife:

  1. besuche einen Scheitelpunkt -> O (1)
  2. a for-Schleife an allen einfallenden Kanten -> O (e) wobei e eine Anzahl von Kanten ist, die auf einen gegebenen Scheitelpunkt v einfallen.

Die Gesamtzeit für eine einzelne Schleife beträgt also O (1) + O (e). Summieren Sie es nun für jeden Scheitelpunkt, da jeder Scheitelpunkt einmal besucht wird. Das gibt

For every V
=> 

    O(1)
    +

    O(e)

=> O(V) + O(E)
Ultrablendz
quelle
2

Kurze aber einfache Erklärung:

Im schlimmsten Fall müssten Sie den gesamten Scheitelpunkt und die Kante besuchen, daher ist die zeitliche Komplexität im schlimmsten Fall O (V + E).

CodeYogi
quelle