코딩테스트에서 요구되는 시간복잡도 어림잡기

온라인 코딩 테스트에서는 제한시간내에 문제의 따른 정확한 값을 반환하는 프로그램을 작성해야한다.

제한시간내에 동작하는 프로그램을 작성하기 위해서 어떻게 해야할까?

컴파일러, 각 컴퓨터의 프로세서의 차이 등이 실행시간에 영향을 끼치겠지만, 컴퓨터는 평균적으로 10**8개의 연산을 1초이내에 수행할 수 있다.

이를 기준으로 시간제한과 주어진 데이터 크기 제한에 따른 시간복잡도를 예측하고 그것에 맞게 답안을 작성하는 편이 더 빠른 솔루션이 있지않을까 고민하는 것 보다 효율적이다.

데이터 크기 제한	예상되는 시간 복잡도
n <= 1,000,000	O(n) or O(n * log(n))
n <= 10,000	O(n**2)
n <= 500	O(n**3)

시간 제한 1~10초내에 데이터 제한 N에 대해 기본연산을 하기 위해 예상되는 시간 복잡도.