DFS Zeitkomplexität (Big-O)

Die Tiefensuche läuft in O(V + E) Zeit und O(V) Speicher und durchsucht einen Graphen so tief wie möglich, bevor sie zurückgeht. Sie liegt topologischer Sortierung und SCC-Algorithmen zugrunde.

Wichtige Fakten

Häufige Fragen

Wie ist die Zeitkomplexität von DFS?

O(V + E), wobei V Knoten und E Kanten sind.

BFS oder DFS?

Beide sind O(V + E); BFS schichtweise, DFS zuerst in die Tiefe.

Verwandte Seiten

• HTTP 200 OK
• HTTP 301 Moved Permanently
• HTTP 401 Unauthorized
• HTTP 403 Forbidden
• HTTP 404 Not Found
• HTTP 429 Too Many Requests
• HTTP 500 Internal Server Error
• HTTP 502 Bad Gateway

Big-O von DFS ist Teil von DevRef Hub auf GOAT Lab — eine kostenlose Referenz, die ohne Anmeldung und auch offline funktioniert. Öffne oben das Tool für beliebige Werte.

Werbung

Teil von GOAT Lab — 26 kostenlose Browser-Tools für Wissenschaft, Technik und Entwicklung. Ohne Anmeldung.