解題的時間複雜度選用

當參加類似 NCPC 的程式競賽, 亦或是解一些 online judge 的題目時

常常會遇到需要考較算法時間的題目

比如排序 10 萬個數時我們自不能把 bubble sort 搬出來用, 否則必將獲得 TLE 一枚XD

所以這篇來介紹一下問題 N 的大小與選用複雜度的關係

因為等寫好才發現解法太慢的話就太浪費時間了

所以會希望在撰寫之前就能有大概的預估時間

而題目幾乎都會指定問題數量的大小

藉此即可來估計時間設計出好的算法

那當然囉,有些題目會設計一些比較詭詐的輸入或是希望你多些優化(即使複雜度可能一樣)

就要對此表做些調整了
 
Part 1.由 N 的大小來選用複雜度 (時限為1秒)

N                Complexity
10               O( N! ), O( N⁶ )
100             O( N⁴ )
1000           O( N³ )
10000         O( N² ) ~ O( N log N )
100000       O( N log N )
1000000     O( N log N ) ~ O( N )
10000000   O( N )
100000000 O(1)
註: 以上僅列出可用之最大複雜度, 如 N=10 時可使用任何比 O( N! ) 快 (如2^N) 的算法

另此以一秒為時限,若時限有加長則有可能可使用略高之算法 (但上表的值通常不會改變,因為即使時間變稍長能用的複雜度仍不會有太大變動)

舉例

UVa 10012 題目大小只到 8,所以我們只要枚舉 8! 種排列再求長度即可,不怕超時
UVa 441 大小 13, 簡單使用6層迴圈解出
UVa 11059 枚舉起點、終點再全部乘起來,總共 O( N³ )
UVa 10107 題目的大小為 10000,所以我們用 insertion sort 就可以用 O( N² ) 來解出
UVa 11858 大小多達一百萬,勢必只能使用 O( N log N ) 的方法解出 inversion 的個數
UVa 12708 因為題目的 N 太大了,所以被迫想 O( 1 ) 的解法,發現只是輸出 N/2 而已

Part 2. 複雜度所能適用的大小 

這裡將不再列舉各例子,請對照上一部份

Complexity  N
O( N! )         12
O( 2^N )        20
O( N⁴ )        100
O( N³ )        1000
O( N² )        10000
O( N log N ) 1000000
O( N )          10000000
O( 1 )           (any)

*這裡一樣假設時限為 1 秒,若時限有多則 N 的大小可增加,但較高的複雜度能增加的大小有限
如同樣由 1 秒增為 2 秒, O( N! ) 能增加的大小就比 O( N ) 少很多