시간복잡도

constraints	time complexity
$n \le 12$	$O(n!)$, $O(n^2 \cdot 2^n)$
$n \le 25$	$O(2^n)$
$n \le 50$	$O(2^{n/2})$
$n \le 100$	$O(n^4)$
$n \le 500$	$O(n^3)$
$n \le 2,000$	$O(n^2 \log{n})$, $O(\dfrac{n^3}{16})$
$n \le 5,000$	$O(n^2)$
$n \le 50,000$	$O(\dfrac{n^2}{64})$
$n \le 100,000$	$O(n \sqrt n)$, $O(n \log^2n)$
$n \le 1,000,000$	$O(n \log n)$
$n \le 5,000,000$	$O(n \log n)$
$n \le 100,000,000$	$O(n)$
$n \gt 10^8 $	$O(\log{n})$, $O(1)$

(  $O(2^{n/2})$은 MITM이고 /16, /64가 붙은건 각각 SIMD, bitset 최적화입니다  )

 

 

c++로 ps를 하는 경우, 보통 초당 $10^8$번의 연산이 가능하다고 가정합니다. 먼저 시간복잡도를 계산한뒤, 입력으로 가능한 최대값을 대입하고 $10^8$ 이하인지 확인함으로써 시간초과 여부를 예측할 수 있습니다.

 

예를 들어보겠습니다.

$O(NQ)$의 코드를 작성했고 $N \le 10^5, Q \le 10^5$라면 $NQ=10^{10}$이므로 시간초과를 받게 될 것입니다.

만약 시간복잡도가 $O(N logN + Q logN)$이라면 $(N+Q)logN = 2 \times 10^5 \times log(10^5) \approx 3 \times 10^6$이므로 시간제한 내에 안전하게 돌 것입니다.

 

제대로 연산횟수를 계산하지 않고 그저 시간복잡도 수식에 대입만 하는 것이라서 부정확할거라 걱정할 수도 있는데, ps에서는 거의 정석으로 통용되는 방식입니다. 만약 계산된 값이 $10^8$ 미만인데 시간초과가 난다면, 무한 루프 같은 로직 실수나 상수 최적화의 문제일 가능성이 큽니다. 하지만 이는 코드를 비효율적으로 짠 것이 문제이지, 풀이의 시간복잡도에 문제가 있는 것이 아닙니다.

 

$10^8$은 꽤나 옛날에 만들어진 기준이라 연산속도가 훨씬 빨라진 지금은 굉장히 보수적인 기준이지만, 그래도 ps에서는 거의 표준으로 굳어진 수치입니다. 정말로 보수적인 기준이기 때문에 계산된 결과가 $10^9$ 근처라도 다른 풀이가 떠오르지 않는다면 일단 제출해보는 것도 좋습니다.

 

이러한 계산방식에 따르면 $N \le 1000$일 때 $O(N^3)$은 시간초과이고, 보통은 $N \le 500$정도가 $O(N^3)$풀이로 가능한 상한선입니다. 요즘은 연산속도가 빨라져 단순계산만 반복하는 경우 $N \le 1000$에서 $O(N^3)$풀이가 뚫리는 경우도 있지만, 이건 말그대로 '뚫은' 것이지 의도된 풀이가 아닐 확률이 높습니다.

 

문제를 풀다 보면 0.1초부터 10초 등 다양한 시간 제한을 마주하게 됩니다. 하지만 문제를 푸는 입장에서는 이 숫자에 너무 민감해질 필요가 없습니다. 앞서 살펴본 $10^8$ 기준표만 잘 지켰다면 대부분의 문제는 무난히 통과되도록 설계되어 있습니다. 보통 이러한 구체적인 시간 제한은 문제를 푸는 사람이 아니라, 문제의 출제자가 고려할 사안입니다. 문제에서 사용되는 알고리즘의 상수가 큰 편이라면 2초~3초 등으로 시간을 널널히 주고, $N \le 1000$인 문제에서 $O(N^2)$풀이를 강제하고 혹시나 $O(N^3)$으로 뚫으려는 사람을 막기 위해 0.1초로 제한하는 등의 경우가 있습니다.