Zeitliche Komplexität der Tiefensuche [geschlossen]

Bitte verzeihen Sie mir, dass ich eine Anfängerfrage gestellt habe, aber ich bin ein Anfänger in Algorithmen und Komplexitäten, und es ist manchmal schwer zu verstehen, wie die Komplexität für einen bestimmten Algorithmus zustande gekommen ist.

Ich habe den DFS-Algorithmus aus Einführung in Algorithmen von Cormen gelesen , und dies war der Algorithmus:

G        -> graph
G.V      -> set of vertices in G
u.π      -> parent vertex of vertex u
G.Adj[u] -> adjacency list of vertex u


DFS(G)
1   for each vertex u ∈ G.V
2       u.color = WHITE
3       u.π = NIL
4   time = 0
5   for each vertex u ∈ G.V
6       if u.color == WHITE
7         DFS-VISIT(G,u)

DFS-VISIT(G,u)
1   time = time + 1            // white vertex u has just been discovered
2   u.d = time
3   u.color = GRAY
4   for each v ∈ G.Adj[u]      // explore edge u
5       if v.color == WHITE
6           v.π = u
7           DFS-VISIT(G,v)
8   u.color = BLACK            // blacken u; it is finished
9   time = time + 1
10  u.f = time

Es sagte dann Zeilen 1-3und 5-7sind O(V), ausschließlich der Zeit, um die Anrufe auszuführen DFS-VISIT(). In DFS-VISIT()Linien 4-7sind O(E), weil die Summe der Adjazenzlisten aller den Eckpunkten die Anzahl der Kanten ist. Und dann kam es zu dem Schluss, dass die Gesamtkomplexität von DFS()ist O(V + E).

Ich verstehe nicht, wie es dazu kam. DFS-VISIT()heißt drinnen DFS() . Wenn also Linien 5-7von DFS()sind O(V)und DFS-VISIT()sind O(E), sollte dann nicht die Gesamtzeitkomplexität von DFS()sein O(VE)?

Das Buch zählt, wie oft jede Zeile während der gesamten Ausführung eines Aufrufs von DFS ausgeführt wird, und nicht, wie oft sie bei jedem Aufruf des Unterprogramms DFS-VISIT ausgeführt wird. Vielleicht macht das folgende einfachere Beispiel dies deutlich:

PROCEDURE A(n)
1  global = 0
2  for i from 1 to n:
3      B(i)
4  return global

PROCEDURE B(i)
1  global = global + 1

Bei jeder Ausführung von A wird Zeile 1 von B ausgeführt $n$ mal und B selbst wird ausgeführt $n$mal. Trotzdem ist die Laufzeit$O(n)$ eher, als $O(n^2)$.

Hier ist ein weiteres Beispiel, in dem ein Array $T[1\ldots n]$ ist involviert.

PROCEDURE COUNT(n, T[1...n]):
1  count = 0
2  index = 1
3  while index <= n:
4    ADVANCE()
5    count = count + 1
6    index = index + 1
7  return count - 1

PROCEDURE ADVANCE():
1  while index <= n and T[index] == 0:
2    index = index + 1

Die Prozedur COUNT zählt die Anzahl der Einsen im Eingabearray T. Auch wenn ADVANCE aufgerufen werden könnte $n$ Zeiten nach COUNT und die Worst-Case-Laufzeit von ADVANCE ist $O(n)$Die Zeilen 1–2 von ADVANCE werden höchstens ausgeführt $n$ Zeiten, und so ist die Gesamtlaufzeit $O(n)$ eher, als $O(n^2)$.