시간 복잡도의 최대값

 * 시간 복잡도의 최대값

각 시간 복잡도별 감당할 수 있는 입력값의 최대값은

입력크기 N 1초 제한 2초 제한
 1. O(1) 상관 없음 상관 없음 상관 없음
 2. O(log n) 10억 수십억 수십억
 3. O(n) 100만 1억 2억
 4. O(nlog n) 10만 10만 15만
 5. O(n^2) 2천 3천 5천
 6. O(n^3) 100 200 230
 7. O(2^n) 20 21
 8. O(n!) 10 11

..~~~~..

 * 1차 첨삭

| 시간 복잡도         | 감당 가능한 N (1초 기준)         | 2초 기준   | 설명                  |
| -------------- | ------------------------ | ------- | ------------------- |
| **O(1)**       | 제한 없음                    | 제한 없음   | 입력 크기와 무관한 고정 시간 연산 |
| **O(log N)**   | 약 1억\~10억                | 수십억     | 이진 탐색 등             |
| **O(N)**       | 약 10⁷\~10⁸ (1억 이하)       | 2억      | 선형 탐색 등             |
| **O(N log N)** | 약 5×10⁵~~10⁶ (50만~~100만) | 100만 이상 | 정렬, 우선순위 큐 등        |
| **O(N²)**      | 약 5천\~1만                 | 최대 1만   | 이중 루프 (브루트포스)       |
| **O(N³)**      | 약 100\~500               | 최대 500  | 삼중 루프 (플로이드 등)      |
| **O(2^N)**     | 약 20\~25                 | 25 이하   | 비트마스크, 백트래킹         |
| **O(N!)**      | 약 10\~11                 | 최대 11   | 순열 완전탐색             |



시간 복잡도 감당 가능한 N (1초 기준) 2초 기준 설명
O(1) 제한 없음 제한 없음 입력 크기와 무관한 고정 시간 연산
O(log N) 약 1억~10억 수십억 이진 탐색 등
O(N) 약 10⁷~10⁸ (1억 이하) 2억 선형 탐색 등
O(N log N) 약 5×10⁵10⁶ (50만100만) 100만 이상 정렬, 우선순위 큐 등
O(N²) 약 5천~1만 최대 1만 이중 루프 (브루트포스)
O(N³) 약 100~500 최대 500 삼중 루프 (플로이드 등)
O(2^N) 약 20~25 25 이하 비트마스크, 백트래킹
O(N!) 약 10~11 최대 11 순열 완전탐색

..~~~~..