Python 시간복잡도, 코드시간측정

# 파이썬으로 여러문제를 풀다보면 시간초과가 나는 일이 많이 발생한다.
    (파이썬은 편리함과 효율성을 맞바꾼 언어라고 누가 그러더라..)

그래서 백준에서는 파이썬으로 채점할 때 (제한시간*3+2)초 이런식으로 시간을 늘려주기는 한다.

그렇지만 항상 코드를 짜면서 내장함수를 사용할때마다 '이 함수는 O(n)인가? O(1)인가?'

이런 고민들을 하게 된다. 

 

1. https://wiki.python.org/moin/TimeComplexity

TimeComplexity - Python Wiki

2. https://www.ics.uci.edu/~pattis/ICS-33/lectures/complexitypython.txt

 

파이썬 메소드들에 관한 시간복잡도가 정리되어있는 사이트이다.

 

# 그런데 여기에 없는 것들도 많아서 검색을 해보았는데 잘 나오지 않아서

      직접 코드수행시간을 확인하는 방법을 검색했다.

 

이런식으로 10번째줄과 14번째 줄 사이에 수행시간이 궁금한 코드를 입력하고 실행하면

이런식으로 시간이 출력된다.

 

3. https://github.com/python/cpython/tree/master/Lib

python/cpython

 

이 github에 들어가면 (경로찾기가 힘들지만) 모든 메소드들의 구성원리를 볼 수 있다.

예를 들면 위에 python wiki에 나오지않는 deque.reverse()같은 경우 O(n/2) = O(n)인것을 확인 할 수있다.