1. PS에서 1초 동안 가능한 연산 횟수
프로그래밍 대회나 알고리즘 문제 풀이에서 시간 제한 1초는 약 1억 번 정도의 연산 수행 제한을 의미합니다.
여기서 말하는 연산은 사칙 연산, 비교 연산, 대입 연산 등으로 이루어진 O(1) 시간에 수행되는 연산을 의미합니다.
이 수치는 실제 CPU가 수행하는 연산 시간이 아니라, 온라인 저지 시스템에서 시간 초과(TLE)를 피하기 위한 기준선입니다.
2. 시간 복잡도에 따른 해결 가능한 입력의 크기
1초에 1억 번의 연산이 가능하다고 했을 때, 시간 복잡도에 따른 1초에 해결 가능한 입력의 크기는 다음과 같이 주먹구구식으로 계산할 수 있습니다.
| 입력 N의 크기 | 시간 복잡도 | 최악의 경우 연산 횟수 |
| \(N \le 11\) | \(O(N!)\) | \(11! = 39,916,800\) |
| \(N \le 25\) | \(O(2^{N})\) | \(2^{25} = 33,554,432\) |
| \( N \le 100 \) | \( O( N^{4} ) \) | \( 100^{4} = 100,000,000 \) |
| \( N \le 500 \) | \( O( N^{3} ) \) | \( 500^{3} = 125,000,000 \) |
| \( N \le 3,000 \) | \( O( N^{2} \lg{N} ) \) | \( 3,000^{2} \lg{3,000} \approx 103,956,721 \) |
| \( N \le 10,000\) | \( O(N^{2}) \) | \(10,000 ^ {2} = 100,000,000\) |
| \( N \le 1,000,000 \) | \( O(N \lg{N}) \) | \( 1,000,000 \lg{1,000,000} \approx 19,931,569 \) |
| \( N \le 10,000,000 \) | \( O(N) \) | \(10,000,000 \) |
| \(N \le 2^{100,000,000}\) | \(O(\lg{n})\) | \( \lg{2^{10^{8}}} = 100,000,000 \) |
| \(N \le \infty\) | \(O(1)\) | 1 |
3. 참고용으로만 사용하기
위에서 작성한 기준표는 참고용에 불과합니다. 그 이유는 다음과 같습니다.
가. O 표기법의 한계
시간 복잡도를 계산할 때는 최고차항 이외의 항들을 모두 지워 버립니다. 따라서 실제 프로그램이 수행하는 반복문의 수는 예상보다 더 커질 수도 있고, 더 작아질 수도 있습니다.
나. 반복문 내부 연산의 다양성
반복문 내부에서 일어나는 연산이 단순한지, 복잡한지에 따라 실제 프로그램이 실행되는 시간이 달라질 수 있습니다. 반복 횟수가 늘어날수록 그 오차는 점점 커질 것입니다.
다. 메모리 사용 패턴의 다양성
메모리에서 캐시로 자료를 가져올 때 인접한 자료들을 함께 가져오기 때문에, 인접한 자료들을 연속해서 사용하는 경우 실제 수행 속도는 빨라집니다. 반대로 인접하지 않는 자료들을 자주 사용할수록 수행 속도는 느려집니다.
