Zeitliche Komplexität der Tiefensuche [geschlossen]

7

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

Sidharth Samant
quelle
6
Cormen ist nur der erste aufgeführte Autor.
Yuval Filmus
1
Willkommen in der Informatik! Ihre Frage ist sehr einfach. Lassen Sie mich Sie auf unsere Referenzfragen hinweisen, die einige Grundlagen abdecken, die Ihnen im Detail zu fehlen scheinen. Bitte bearbeiten Sie die dort aufgeführten Fragen, versuchen Sie, Ihr Problem erneut zu lösen, und bearbeiten Sie sie, um Ihre Versuche zusammen mit den spezifischen Problemen, auf die Sie gestoßen sind, einzuschließen. Viel Glück!
Raphael
Könnten Sie das genaue Zitat des Textes geben, den Sie nicht verstehen? Wenn wörtlich "exklusiv für die Zeit, in der die Anrufe ausgeführt werden sollen DFS-VISIT()" steht, wird Ihre Frage bereits beantwortet: "exklusiv für DFS-VISIT()" bedeutet, dass die angegebene Zeit nicht die von enthaltene Zeit enthält DFS-VISIT().
David Richerby

Antworten:

8

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 nmal. Trotzdem ist die LaufzeitO(n) eher, als O(n2).

Hier ist ein weiteres Beispiel, in dem ein Array T[1n] 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(n2).

Yuval Filmus
quelle
Ähm ... ich kann es immer noch nicht verstehen. Zeitkomplexität für B()ist O(1), wenn ialso von aufgerufen wird 1 to n, dann ist es n-mal O(1)-> O(n). Sie sagen, Zeile 1 von B wird n- mal ausgeführt und B selbst wird n- mal ausgeführt, aber sind sie nicht dasselbe?
Sidharth Samant
Sie sind in diesem Beispiel dasselbe, jedoch nicht im Fall von DFS.
Yuval Filmus
1
Ich habe ein weiteres Beispiel hinzugefügt, das dem in DFS ähnlicher ist.
Yuval Filmus
Yuval sir @ ich habe Zweifel. In Ihrem bereitgestellten Beispielalgorithmus, was wäre wenn A wird genannt n Zeiten, die impliziert O(n2)Sir, bitte helfen Sie mir!
Laura
1
Ausführen eines Θ(f(n)) Verfahren g(n) Zeiten brauchen Zeit Θ(f(n)g(n)).
Yuval Filmus