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를 수행하는 기능을 보냈다.