시간복잡도

for문이 1억번 도는데 1초정도의 시간이 소요됨

- 제한 시간이 1초인 문제를 풀 때 대략 1억 이하의 시간복잡도를 보이는 솔루션이면 통과 가능하다

N <= 10 일 때 시간이 가장 오래 걸리는 최악의 상왕에서 시간복잡도를 살펴보면, O(N!) 솔루션은 최대 10! 시간이 걸린다는 뜻이다. 10! = 3628800 < 1억 이므로 제한 시간 내에 통과 가능하다.

N <= 20 일 때 O(2^N) 솔루션 사용시 최대 2^20 의 시간이 소요된다. 2^20 = 1048576 < 1억이다. 1초안에 통과 가능하다.

N <= 1000일 때 O(N^2logN) 솔루션 사용시 최대 1000^2 *  log1000 < 1억으로 1초안에 통과 가능

N <= 100000 일 때 O(N*2)를 사용하면 최대 10^10으로 1억보다 크다. 1초 안에 통과 불가.