wake-up-neo.com

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

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)

wobei v der Scheitelpunkt 1 zu n ist

Erstens ist das, was ich gesagt habe, richtig? Zweitens, wie ist das O(N + E) und warum wäre das wirklich nett? Vielen Dank

algorithmtime-complexitygraph-theorybreadth-first-search
117
ordinary

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 O(E) ist.

244
Mihai Maruseac

DFS (Analyse):

  • Das Setzen/Abrufen eines Scheitelpunkts/Kantenlabels nimmt O(1) Zeit in Anspruch
  • Jeder Scheitelpunkt ist doppelt beschriftet
    • einmal als unerforscht
    • einmal als BESUCHT
  • Jede Kante ist doppelt beschriftet
    • einmal als unerforscht
    • einmal als ENTDECKUNG oder ZURÜCK
  • Die Methode incidentEdges wird für jeden Scheitelpunkt einmal aufgerufen
  • DFS wird in der O(n + m) -Zeit ausgeführt, sofern das Diagramm durch die Adjazenzlistenstruktur dargestellt wird
  • Denken Sie daran, dass Σv deg(v) = 2m

BFS (Analyse):

  • Das Setzen/Abrufen eines Scheitelpunkts/Kantenlabels dauert O(1) Zeit
  • Jeder Scheitelpunkt ist doppelt beschriftet
    • einmal als unerforscht
    • einmal als BESUCHT
  • Jede Kante ist doppelt beschriftet
    • einmal als unerforscht
    • einmal als ENTDECKUNG oder KREUZ
  • Jeder Vertex wird einmal in eine Sequenz Li eingefügt
  • Die Methode incidentEdges wird für jeden Scheitelpunkt einmal aufgerufen
  • BFS wird in der O(n + m) -Zeit ausgeführt, sofern der Graph durch die Adjazenzlistenstruktur dargestellt wird
  • Denken Sie daran, dass Σv deg(v) = 2m
37
TheNewOne

Ohne viel Formalität sehr vereinfacht: 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.

18
JavaFreak

Die Zeitkomplexität ist O(E+V) anstelle von O(2E+V), denn wenn die Zeitkomplexität n ^ 2 + 2n + 7 ist, 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.

10
Dhruvam Gupta

Ich denke, jeder Edge wurde zweimal in Betracht gezogen und jeder Knoten wurde einmal besucht, daher sollte die Gesamtzeitkomplexität O (2E + V) sein.

3
Kehe CAI

Kurze aber einfache Erklärung:

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

2
CodeYogi

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

  1. einen Eckpunkt besuchen -> O (1)
  2. eine for-Schleife für alle 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 sie nun für jeden Scheitelpunkt, da jeder Scheitelpunkt einmal besucht wird. Das gibt

Sigma_i

p {
    height: 50px;
    line-height: 50px;
}

span {
    position: relative;
    font-size: 2.5em;
    display: inline-block;
    line-height: .7em;
    vertical-align: middle;
}

span:before {
    font-size: 12px;
    display: block;
    position absolute;
    left: 0;
    top: 0;
    content: "V";
    width: 22px;
    text-align: center;
}

span:after {
    font-size: 12px;
    display: block;
    position absolute;
    left: 0;
    bottom: 0;
    content: "k = 1";
    width: 27px;
    text-align: center;
}
<p>
    <span>&Sigma;</span>
    O(1) + O(e)
=> 
    <span>&Sigma;</span>
    O(1)
    +
   <span>&Sigma;</span>
    O(e)

=> O(V) + O(E)

</p>

[O(1) + O (e)]

2
Ultrablendz