p.593 시간복잡도 관련 질문입니다.

[PudgeKim]

p.593 시간복잡도 관련 질문입니다.

[likejazz]

여기서 실행 속도는 시간 복잡도 보다는 모듈의 실행 속도에 훨씬 더 큰 영향을 받습니다.

일반적으로 파이썬 내장 모듈의 실행 속도는 파이썬으로 직접 구현하는 것에 비해 100배 이상 빠른 경우도 많습니다. 왜냐면 파이썬은 모든 것이 객체이기 때문에 불필요한 오버헤드가 많지만 내장 모듈은 C로 꼭 필요한 연산만 수행하고 이 마저도 꾸준히 최적화가 이뤄지고 있기 때문에 매우 빠르게 동작합니다. (p119 동일한 연산의 시간 비교 참고)

책에서는 heapq 모듈에서 거의 모든 연산을 진행한데 반해 제시해주신 코드에서는 직접 파이썬으로 O(n^2) 연산을 수행합니다. 이 경우 시간 복잡도가 아무리 좋아도 파이썬 자체의 느린 속도로 인해 손해를 보는 경우가 많습니다. 만약 모든 코드를 C로 작성한다면 더 빠르게 동작할 수 있겠으나 여기서는 C로 작성된 내장 모듈과 파이썬으로 직접 구현한 알고리즘 간에 기본적인 속도 차이가 존재합니다.