https://blog.naver.com/tndus4243

반복문이 한번: O(n)

중첩 반복문: O(n^2)

이분 탐색: O(logn)

언어에서 기본적으로 제공되는 정렬: O(nlogn)

외판원:O(n!)

선택정렬:O(n^2)

제한 시간이 1초인 문제에 대한 예시이다.

• N의 범위가 500인 경우 : 시간 복잡도가 O(N^3)인 알고리즘으로 설계하면 풀이 가능
• N의 범위가 2,000인 경우 : 시간 복잡도가 O(N^2)인 알고리즘으로 설계하면 풀이 가능
• N의 범위가 100,000인 경우 : 시간 복잡도가 O(NlogN)인 알고리즘으로 설계하면 풀이 가능
• N의 범위가 10,000,000인 경우 : 시간 복잡도가 O(N)인 알고리즘으로 설계하면 풀이 가능

코딩테스트 문제의 시간제한은 대략 5초

Python이 초당 2000만번의 연산만 가능하다고 가정하는 것이 좋음

5초에 1억번