python - 深度优先搜索运行时测量

Question

我目前正在研究深度优先搜索算法，虽然我已经确认它确实在 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

应该显示实际执行 DFS 的函数所花费的总时间 (tottime)。