時間複雜度(大O)比較工具

以具體的次數與時間,顯示演算法的時間複雜度(大O符號)不同時,資料增加後處理時間會相差多少。輸入資料數與電腦每秒可處理的次數,即可知道各複雜度所需的時間。也能估算資料數改變時的處理時間。

資料數與處理速度

資料數改變時的估算

步驟次數的比
–
新的處理時間估計
–

各複雜度的次數與時間

資料數與步驟次數(縱軸為對數)

步驟次數是直接以忽略係數與常數項的複雜度式子(log 以 2 為底)計算。實際時間會因係數、記憶體與快取的速度、輸入的排列方式等而改變,請作為參考。圖表顯示到資料數 60 為止,超過 10¹² 次的部分會截掉。

什麼是大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 超過數十後就無法在實際可行的時間內完成,因此會使用動態規劃或近似演算法等方法減少次數。

練習演算法題目

對於有 n 個元素的陣列,將所有不同的兩個元素組合各比較一次的處理(以雙重迴圈將第 i 個元素與其後的所有元素比較,並讓 i 逐一前進),其時間複雜度為下列何者?

  1. AO(n)
  2. BO(n log n)
  3. 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) 則是像合併排序那樣反覆對半分割的處理的複雜度。

某個時間複雜度為 O(n²) 的程式,在資料數為1,000時處理時間為0.5秒。若資料數變為4,000,處理時間約為幾秒?

  1. A2秒
  2. B8秒
  3. C32秒
查看答案與解析

正確答案:B. 8秒

O(n²) 的處理時間與資料數的平方成正比,因此資料數變為4倍時,處理時間變為 4² = 16倍,0.5秒 × 16 = 8秒。2秒是與資料數成正比的 O(n) 的情況,32秒則是與立方成正比的 O(n³) 的情況(4³ = 64倍)。實際上,也可能因資料放不進快取等影響而變得更慢。

以從開頭逐一比較的線性搜尋,在存有100個不同值的陣列中尋找目標值。若目標值一定在陣列中,且位於各位置的機率相等,則比較次數的平均為多少?

  1. A約7次
  2. B50.5次
  3. 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,是二分搜尋的次數,但資料未排序時無法使用。

以二分搜尋在依升冪排序的1,000個不同值中尋找某個值。若1次比較就能得知「相等、較小、較大」,包含找得到與找不到的情況,比較次數最多為幾次?

  1. A10次
  2. B32次
  3. 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)。

考試中會怎麼出題?

日本基本資訊技術士考試等資訊類證照考試,常考資料數改變時處理時間的估算、選出演算法的時間複雜度,以及複雜度大小順序的題目。可在下方「估算」欄輸入題目中的數值來確認。

相關術語

時間複雜度(大O符號) 二分搜尋 動態規劃

相關計算工具

半導體、電子電路與資訊計算工具 →