코테 시간 복잡도 계산방법

n으로 구성된 시간복잡도 O( )를 계산했을 때의 값이 1억 정도면 1초 정도의 시간이 걸린다고 한다. 

1억에 1초

물론 이 값이 완전 정확한 것은 아니기에, 

문제와 알고리즘에 따라서 달라질 수 있는 것이지만 

보통 자신의 알고리즘이 몇 초안에 끝날지를 계산하기 위해서는 

1억 정도의 값이 1초라는 것을 알면 계산이 쉽다!

 

예를 들어 N의 최대 값이 10만일 때,(10만 ,100만, 1000만, 억)

1. O(N)의 시간복잡도일 경우에 값이 10만 정도이니, 1/1000초 정도가 걸릴 것이라 예상

2. O(N^2)의 시간복잡도의 경우에 값은 100억이므로, 100초 정도가 걸릴 것이라고 예상

 

이 경우 문제 제한 시간이 1초라면 O(N^2)의 시간복잡도를 갖는 알고리즘으로 문제를 풀 수 없다는 것을

미리 파악해야한다. 

 

입력값(N)의 최대크기

O(N)	약 1억
O(N²)	약 1만 (10,000)
O(N³)	약 500
O(𝟐ⁿ)	약 20
O(N!)	10