Depth-First Searchランタイム測定

Question

現在Depth-First Searchアルゴリズムを研究していますが、O（N + M）で実行されていることを確認しましたが、ランタイムを測定すると表示されませんこれは、2000〜16000ノードのグラフと一定の50000エッジのグラフのためです。ランタイムは、ノードが多くのことをしていないかのように、ほぼ一定（0.5秒に近い）のままです。あまりにも多くのノードを追加することなく、ランタイムにさらに重要な変更を加える方法はありますか？

私はPythonで実装を使用しており、 "time"コマンドを使用してランタイムを測定しています。

Answer 1

問題は、Pythonに比較的高いオーバーヘッド（プログラムの読み取りと解析）があることが原因です。この質問を確認する：How can you profile a python script?

具体的には、

python -m cProfile myscript.py 

は合計時間（tottime）が、実際にDFSを行う機能に費やさあなたが表示されるはずです。