Warum wird die Zeit, die Komplexität der DFS und BFS abhängen, wie der graph dargestellt wird?
Die Website http://web.eecs.utk.edu/~huangj/CS302S04/notes/graph-searching.html beschreibt, dass, wenn ein angrenzens Liste wird dann verwendet, DFS-und BFS haben die Komplexität O(V+E), und wenn eine Nachbarschaft-matrix verwendet wird, die Komplexität ist O(V2). Warum ist das so?
- Diese Frage scheint off-topic, weil es nicht über ein computer Programm oder eine Programmiersprache.
Schreibe einen Kommentar
Du musst angemeldet sein, um einen Kommentar abzugeben.
In beiden Fällen die Laufzeit hängt davon ab, wie lange es dauert, bis die Iteration über die ausgehenden Kanten von einem gegebenen Knoten. Mit einem angrenzens Liste, die Laufzeit ist direkt proportional zu der Anzahl der ausgehenden Kanten. Weil jeder Knoten einmal besucht wird, die Kosten ist die Anzahl der Knoten plus die Anzahl der Kanten, die in O(m + n). Mit am angrenzens matrix, die erforderliche Zeit zu finden, alle ausgehenden Kanten ist O(n), da alle n-Spalten in der Zeile eines Knotens geprüft werden muss. Aufsummieren über alle n Knoten, das sind O(n2).
Hoffe, das hilft!
Müssen Sie beachten, dass für die Erkundung ur jeden Knoten die benötigte Zeit für die Erkundung ist es nur gleich c*x, wobei x ist die indegree des vertex.Da wir interessiert sind, die gesamte Komplexität, die gesamte Zeit wäre c1*x1+c2*x2...cnxn für n Knoten.Wobei max(ci)=d,sehen wir, dass die gesamte Zeit ist <=d(Summe der indegrees der alle vertices)=d*2m=O(m).Hier haben wir berechneten die Zeit nicht für eine Ecke, aber alle Eckpunkte zusammen gefasst.Aber das einreihen operation kostet Zeit O(n), so overalll O(n+m).
Die Zeit-Komplexität für beide DFS-und BFS berechnet werden kann wie folgt:
Durchlaufen jede Ecke einmal und Ihre entsprechenden inzidenten Kanten, so dass die Gesamtzeit, die Komplexität wird ->
Zeit Komplexität = v1 + (incident_edges auf v1) + v2 + (incident_edges auf v2) + ...... + vn + ( incident_edges auf vn)
Nun dies kann zusammengefasst werden als -> (v1+v2+v3+.....vn) + (incident_edges auf v1 + incident_edges auf v2 + ..... incident_edges auf vn)
Somit insgesamt Zeit Komplexität erweisen würde = (v1+v2+v3+.....vn) + (incident_edges auf v1 + incident_edges auf v2 + ..... incident_edges auf vn)
(v1 + v2 + ... + vn) = V oder n (Gesamtzahl der Ecken)
Für Nähe Listendarstellung :
(incident_edges auf v1 + incident_edges auf v2 + ..... incident_edges an vn) = E(Gesamtzahl der Ecken)
Somit für angrenzens Liste Darstellung Zeit-Komplexität O(V+E)
Für Nähe matrix-Darstellung :
Besuch der Nachbarn des entsprechenden Knoten(Zeile) müssen wir Durchlaufen alle Spalten für die jeweilige Zeile die Mengen zu V
So, (incident_edges auf v1 + incident_edges auf v2 + ..... incident_edges an vn) = V + V + .... Vth Zeit, V) = V*V
Somit Zeit-Komplexität O(V + V^2) = O(V^2)