時間複雜度(大O)比較工具
以具體的次數與時間,顯示演算法的時間複雜度(大O符號)不同時,資料增加後處理時間會相差多少。輸入資料數與電腦每秒可處理的次數,即可知道各複雜度所需的時間。也能估算資料數改變時的處理時間。
各複雜度的次數與時間
資料數與步驟次數(縱軸為對數)
步驟次數是直接以忽略係數與常數項的複雜度式子(log 以 2 為底)計算。實際時間會因係數、記憶體與快取的速度、輸入的排列方式等而改變,請作為參考。圖表顯示到資料數 60 為止,超過 10¹² 次的部分會截掉。
以圖表檢視
其他輸入維持目前的值,只讓選擇的輸入在目前值的 1/4 到 4 倍之間變化時的結果。紅點是目前的值。
什麼是大O符號
大O符號(O 符號)表示資料數 n 變大時,演算法的步驟次數以什麼比例增加。例如需要 3n² + 5n + 2 次步驟時,n 很大時 n² 項占主導地位,因此忽略係數與較小的項,寫成 O(n²)。如此一來,就能不受電腦速度或實作細節影響,比較演算法之間的效率。
複雜度不同所造成的差異
假設每秒可處理 1 億次,n = 100 萬時,O(n) 只需 0.01 秒,O(n log n) 約 0.2 秒,但 O(n²) 需要 1 萬秒(約 2.8 小時)。O(2ⁿ) 即使 n = 50 也需要約 130 天,而且 n 每增加 1,時間就變為 2 倍。資料少的時候每一種都瞬間完成,差異不容易看出,資料增加後才會成為問題。請將資料數改為 1000、100 萬、10 億,比較表格中時間一欄的變化。
處理時間的估算
知道時間複雜度,就能估算資料數改變時的處理時間。若 O(n²) 的程式在資料數 1000 時需要 0.5 秒,資料數 4000 時次數會變為 (4000 ÷ 1000)² = 16 倍,因此可估算約為 8 秒。若是 O(n log n),則為 4000 × log₂ 4000 ÷ (1000 × log₂ 1000) ≒ 4.8 倍,約 2.4 秒。考試中常出現這類估算,或問哪一種複雜度較快的順序。
常用演算法的時間複雜度
二分搜尋每次將要檢查的範圍減半,因此為 O(log n)。已知以比較進行的排序,在最差情況下不可能比 O(n log n) 更快,合併排序與堆積排序達到這個極限。直接計算 n × n 矩陣的乘積為 O(n³)。O(2ⁿ) 或 O(n!) 這類指數時間的演算法,n 超過數十後就無法在實際可行的時間內完成,因此會使用動態規劃或近似演算法等方法減少次數。
練習演算法題目
- AO(n)
- BO(n log n)
- CO(n²)
查看答案與解析
正確答案:C. O(n²)
比較的組數為 (n−1) + (n−2) + … + 1 = n(n−1)/2,n = 10 時為45次,n = 1000 時為499,500次。時間複雜度的階只看 n 變大時的增加方式,因此省略係數1/2與低次項,表示為 O(n²)。n 變為2倍時,次數約變為4倍。O(n) 是每個元素只看一次的處理,O(n log n) 則是像合併排序那樣反覆對半分割的處理的複雜度。
- A2秒
- B8秒
- C32秒
查看答案與解析
正確答案:B. 8秒
O(n²) 的處理時間與資料數的平方成正比,因此資料數變為4倍時,處理時間變為 4² = 16倍,0.5秒 × 16 = 8秒。2秒是與資料數成正比的 O(n) 的情況,32秒則是與立方成正比的 O(n³) 的情況(4³ = 64倍)。實際上,也可能因資料放不進快取等影響而變得更慢。
- A約7次
- B50.5次
- C100次
查看答案與解析
正確答案:B. 50.5次
目標值在第 k 個位置時要比較 k 次,因此平均為 (1 + 2 + … + 100) / 100 = 50.5次,一般而言為 (n + 1)/2 次。最佳情況(位於開頭)為1次,最差情況(位於末尾)為100次,平均與最差都與 n 成正比,因此時間複雜度為 O(n)。約7次相當於 log₂ 100 ≈ 6.6,是二分搜尋的次數,但資料未排序時無法使用。
- A10次
- B32次
- C500次
查看答案與解析
正確答案:A. 10次
每比較1次,搜尋範圍約減為一半,而 2¹⁰ = 1024 ≥ 1000,因此最多10次範圍就會用盡(⌊log₂ 1000⌋ + 1 = 10)。時間複雜度為 O(log n),即使有100萬個也最多只需20次。32次相當於 √1000 ≈ 31.6,500次則接近線性搜尋的平均(約 n/2)。不過,二分搜尋需要資料已排序,也必須考慮排序所需的 O(n log n) 工作量。
常見問題
O(log n) 的 log 是以什麼為底?
在大O符號中,底數不同只會造成常數倍的差異,因此通常不寫底數。本工具配合二分搜尋等的步驟次數,以 2 為底。
O(n²) 的演算法一定比 O(n log n) 慢嗎?
資料數少時,係數小的 O(n²) 演算法有時反而較快。因此實際的排序實作,有時會在排序短的區段時使用插入排序。資料數變大後,複雜度較小的一方一定較有利。
什麼是空間複雜度?
表示演算法所使用的記憶區域(記憶體)量如何增加。例如合併排序需要 n 個元素份的工作區,因此空間複雜度為 O(n);堆積排序在陣列內重新排列,因此為 O(1)。
考試中會怎麼出題?
日本基本資訊技術士考試等資訊類證照考試,常考資料數改變時處理時間的估算、選出演算法的時間複雜度,以及複雜度大小順序的題目。可在下方「估算」欄輸入題目中的數值來確認。