Depth-First Search Laufzeitmessung

Question

Ich untersuche gerade den Tiefensuchalgorithmus und obwohl ich bestätigt habe, dass es in O (N + M) läuft, wird es immer noch nicht sehr gut angezeigt, wenn ich die Laufzeit messe , da in einem Graph mit 2000 bis 16000 Knoten und einer konstanten 50000 Kanten. Die Laufzeit bleibt nahezu konstant (knapp 0,5 Sekunden), als ob die Knoten nicht viel tun würden. Gibt es eine Möglichkeit, eine bedeutendere Änderung der Laufzeit zu erreichen, ohne zu viele weitere Knoten hinzuzufügen?

Ich verwende eine Implementierung in Python und mit dem Befehl "Zeit", um die Laufzeit zu messen.

Answer 1

Das Problem kann sein, dass Python relativ hohen Aufwand hat (Lesen und Analysieren des Programms). Überprüfen Sie diese Frage: How can you profile a python script?. speziell

Mehr,

python -m cProfile myscript.py 

sollten Sie die Gesamtzeit zeigen (tottime) verbrachte auf die Funktion, die die DFS tatsächlich der Fall ist.