ICRACK 個人部落格

Loading...

N 的範圍估算

假設 C++ 一秒可以處理約 $10^{6}$ 次基本操作
我們可以根據不同時間複雜度
推算在 1 秒內可以接受的輸入規模 $N$
(通常題目時間限制是 1 秒)

時間複雜度 (Big O)	可接受的最大 N（估計）
$O(1)$	幾乎無限制
$O(lonN)$	幾乎無限制
$O(\sqrt{N})$	$N \leq 10^{12}$
$O(N)$	$N \leq 10^{6}$
$O(NlogN)$	$N \leq 10^{6}$
$O(N^{2})$	$N \leq 10^{4}$
$O(N^{3})$	$N \leq 500$
$O(2^{N})$	$N \leq 25$
$O(N!)$	$N \leq 10$

前言

基礎

算法