複雜度

總結

自己寫一個小程式
令 \(O(f(n))\) 是時間複雜度
算算看 n ="範圍" 帶入 \(f(n)\) 是否會超過 7 位數 (7 位數是可接受的)
也就是 \(f(n)<1*10^8=1e8\)

自己

口訣：一二五百千萬

Big-O 複雜度	競賽適用範圍
\(O(n!)\)	\(n \leq 10\)
\(O(2^n)\)	\(n \leq 20\)
\(O(n^4)\)	\(n \leq 50\)
\(O(n^3)\)	\(n \leq 百位數\)
\(O(n^2)\)	\(n \leq 千位數\)
\(O(n \log n)\)	\(n \leq 萬以上\)

IONC

每秒 \(10^7\)

Big-O 複雜度	競賽適用範圍
\(O(n!)\)	\(n \leq 10\)
\(O(2^n)\)	\(n \leq 20\)
\(O(n^4)\)	\(n \leq 50\)
\(O(n^3)\)	\(n \leq 200\)
\(O(n^2)\)	\(n \leq 3000\)
\(O(n \log n)\)	\(n \leq 10^6\)（有時候 \(n = 10^7\) 也不會 TLE）

\(O(n!)\)\(O(2^n)\)\(O(n^4)\)\(O(n^3)\)\(O(n^2)\)\(O(n \log n)\)

\(n \leq 10\)

9 : 362880
10 : 3628800
11 : 39916800

\(n \leq 20\)

19 : 524288
...
22 : 4194304
23 : 8388608
24 : 16777216

\(n \leq 50\)

45 : 4100625
...
55 : 9150625
56 : 9834496
57 : 10556001

\(n \leq 200\)

190 : 6859000
...
214 : 9800344
215 : 9938375
216 : 10077696

\(n \leq 3000\)

3000 : 9000000
...
3161 : 9991921
3162 : 9998244
3163 : 10004569

\(n \leq 10^6\)（有時候 \(n = 10^7\) 也不會 TLE）

739949 : 9.99992e+006
739950 : 9.99993e+006
739951 : 9.99995e+006
739952 : 9.99996e+006
739953 : 9.99998e+006
739954 : 9.99999e+006
739955 : 1e+007
739956 : 1e+007

e+007= *\(10^7\)

AP325

Big-O 複雜度	競賽適用範圍
\(O(n!)\)	10
\(O(2^n)\)	20~25
\(O(n^4)\)	無
\(O(n^3)\)	數百
\(O(n^2)\)	數千
\(O(n)\) or \(O(n \log n)\)	超過1萬