파이썬 시간복잡도

안녕하세요. 알고리즘 문제를 풀때에 파이썬 시간복잡도 시간을 확인하는 방법을 알려드리겠습니다.

 

파이썬은 1초에 2000만 = 20,000,000 번 연산이 가능하다고 생각해두면 좋습니다.

따라서 시간제한이 1초, n = 100,000 (10만) 이라고 할 때

O(N^2) 으로 알고리즘을 짜게 되면 10,000,000,000 = 100억 번의 연산이 필요하므로, 시간초과가 나게 된다.

이 경우엔 O(NlogN) 으로 알고리즘을 짜야 1,600,000 번의 연산으로 문제를 해결해야합니다.