10^8 경험칙

일반적인 온라인 채점 시스템은 초당 약 10^8개의 단순한 연산을 수행합니다. 이 숫자가 프로그램 전체에 사용할 수 있는 연산 예산입니다. 💡

연산 횟수에 단계당 작업량을 곱한 뒤 시간 제한과 비교하십시오. 연산 횟수가 예산 안에 들어오면 통과할 가능성이 높습니다.

n = 10^6일 때 O(n)으로 순회해도 백만 단계에 불과하여 예산보다 훨씬 적습니다. 선형 해법은 거의 항상 여유 있게 통과합니다.

n = 10^6일 때 O(n log n) 정렬은 약 2 × 10^7단계입니다. 여전히 1초 예산 안에 충분히 들어오므로 정렬이 병목이 되는 경우는 드뭅니다.

O(n^2) 방식은 n = 10^4 부근에서 예산에 도달하며, 이때 10^8단계가 필요합니다. 그보다 커지면 이차 시간 방식은 시간 초과가 발생하기 시작합니다.

O(n^3) 해법은 n이 약 500일 때까지만 버팁니다. 이를 세제곱하면 대략 10^8단계에 도달하여 예산의 한계에 이릅니다.

O(2^n)은 단계마다 두 배가 되므로 n이 20에서 25 정도로 아주 작을 때만 작동합니다. 그보다 커지면 연산 횟수가 10^8을 넘어 폭발적으로 증가합니다.

Python은 단계당 속도가 느리므로 빡빡한 반복문에서는 예산을 10^7에 가깝게 잡으십시오. 제한이 아슬아슬해 보일 때는 보수적으로 판단하십시오.

10^8 규칙은 단순한 단계만 셉니다. 문자열 만들기처럼 반복문 안에서 무거운 작업을 수행하면 상수 배수가 추가되어 실제 예산이 줄어듭니다.

시간 제한은 보통 1초 또는 2초입니다. 2초 제한은 예산을 대략 두 배로 늘려 조금 더 여유를 줍니다.

항상 먼저 n을 복잡도에 대입하고 10^8과 비교하십시오. 이 빠른 타당성 점검으로 실패할 해법을 작성하는 일을 피할 수 있습니다.

10^8 규칙을 적용해 보십시오.

이제 연산을 시간으로 환산할 수 있습니다. 초당 대략 10^8회입니다. 선형과 n log n은 안전하고, 이차 시간은 10^4 부근에서 한계에 이르므로 코딩 전에 확인하십시오. ✅