Die Seite Ссылка beschreibt, dass wenn eine Adjazenzliste dann verwendet wird DFS und BFS haben Komplexität O (V + E), und wenn eine Adjazenzmatrix verwendet wird, ist die Komplexität O (V 2). Warum ist das?
In beiden Fällen hängt die Laufzeit davon ab, wie lange es dauert, über die ausgehenden Kanten eines bestimmten Knotens zu iterieren. Bei einer Adjazenzliste ist die Laufzeit direkt proportional zur Anzahl der ausgehenden Kanten. Da jeder Knoten einmal besucht wird, sind die Kosten die Anzahl der Knoten plus die Anzahl der Kanten, die O (m + n) ist. Bei einer Adjazenzmatrix ist die Zeit, die erforderlich ist, um alle ausgehenden Kanten zu finden, O (n), da alle n Spalten in der Reihe für einen Knoten inspiziert werden müssen. Zusammenfassend ergibt sich dies für alle n Knoten zu O (n 2 ).
Hoffe, das hilft!
Sie müssen beachten, dass zum Erkunden jeder für die Untersuchung erforderlichen Eckpunktzeit nur gleich c * x ist, wobei x die Unabhängigkeit des Eckpunkts ist. Da wir an der Gesamtkomplexität interessiert sind, wäre die Gesamtzeit c1 * x1 + c2 * x2 ... cn xn für n Knoten. Wenn wir max (ci) = d nehmen, sehen wir, dass die Gesamtzeit & lt; = d (Summe der Indegre aller Ecken) = d * ist 2m = O (m) .Hier haben wir die Zeit für nicht einen Scheitelpunkt, aber alle Scheitelpunkte zusammen berechnet. Aber die Einreihungsoperation benötigt Zeit O (n), also insgesamt O (n + m).
Tags und Links graph-algorithm data-structures time-complexity graph breadth-first-search