繁體中文
選單

什麼是時間複雜度（大O符號）

表示演算法所需的工作量（時間複雜度）或記憶空間（空間複雜度），隨資料數 n 如何增加的指標。以 O(n)、O(n log n)、O(n²) 這類大O符號表示，省略係數與低次項。

日文名稱: 計算量

「時間複雜度（大O符號）」出現在1領域的7道練習題中（資料結構與演算法等）。

這個名詞所屬的領域: 資料結構與演算法

大O符號的讀法

O(f(n)) 表示當 n 夠大時，工作量大約不超過 f(n) 的常數倍。比較次數為 3n² + 5n + 2 次的演算法，在 n 變大時 n² 項占主導地位，因此寫成 O(n²)。常見的由小到大依序為 O(1)（常數）、O(log n)（二分搜尋）、O(n)（線性搜尋）、O(n log n)（合併排序、堆積排序）、O(n²)（泡沫排序、選擇排序）、O(2ⁿ)（單純的窮舉搜尋）等。n = 1000 時，log₂ n 約為10，n log₂ n 約為1萬，n² 為100萬，因此資料量大時，複雜度的差異具有決定性。

最佳、平均與最差情況

即使是相同的演算法，工作量也可能隨輸入而改變。插入排序對已排序的資料只需比較 n−1 次，為 O(n)，但對反序資料需要 n(n−1)/2 次，為 O(n²)。快速排序平均為 O(n log n)，但視樞紐的選法與資料而定，最差會變成 O(n²)。需要回應時間上限的系統重視最差情況，估算整體處理量時則重視平均情況。像可變長度陣列的加入這樣，偶爾有較重的處理、但多次平均下來為定值的情況，以攤銷複雜度 O(1) 表示。

實際速度不只由複雜度決定

大O符號忽略常數倍，因此即使同樣是 O(n)，實際速度也可能相差很大。在現今的電腦中，存取主記憶體比 L1 快取慢將近100倍，因此依序讀取陣列的處理比走訪鏈結串列快好幾倍。此外，n 較小時，複雜度較大的單純方法反而可能較快，實際的排序實作會在短區間使用插入排序。改善效能時，應先確認是否使用了複雜度過大的演算法，再量測並調整記憶體存取方式等細節。

練習時間複雜度（大O符號）的題目

對於有 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倍）。實際上，也可能因資料放不進快取等影響而變得更慢。

常見問題

O(log n) 中 log 的底數是多少？

換底只會相差常數倍（log₂ n = log₁₀ n ÷ log₁₀ 2），因此大O符號通常不寫底數。像二分搜尋這樣每次分成一半的情況，實際次數接近 log₂ n。

時間複雜度與空間複雜度有什麼不同？

時間複雜度是工作量（執行時間）的增加方式，空間複雜度是所需記憶空間的增加方式。例如合併排序為時間 O(n log n)、工作空間 O(n)，堆積排序為時間 O(n log n)、空間 O(1)，兩者要一起比較。

解析中的「時間複雜度（大O符號）」

出現「時間複雜度（大O符號）」的題目（7題）

  1. 對於有 n 個元素的陣列，將所有不同的兩個元素組合各比較一次的處理（以雙重迴圈將第 i 個元素與其後的所有元素比較，並讓 i 逐一前進），其時間複雜度為下列何者？
  2. 某個時間複雜度為 O(n²) 的程式，在資料數為1,000時處理時間為0.5秒。若資料數變為4,000，處理時間約為幾秒？
  3. 即使在最差情況下時間複雜度也是 O(n log n)，且幾乎不使用工作用陣列等額外記憶體就能排序的演算法為下列何者？
  4. 快速排序的時間複雜度變成 O(n²) 的典型情況為下列何者？
  5. 以從開頭逐一比較的線性搜尋，在存有100個不同值的陣列中尋找目標值。若目標值一定在陣列中，且位於各位置的機率相等，則比較次數的平均為多少？
  6. 以二分搜尋在依升冪排序的1,000個不同值中尋找某個值。若1次比較就能得知「相等、較小、較大」，包含找得到與找不到的情況，比較次數最多為幾次？
  7. 在元素很多、負載因子維持在0.5左右的雜湊表中，使用線性探測的開放定址法往往比鏈結法（以鏈結串列串接的方法）快，最適當的原因為下列何者？

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

排序演算法視覺化工具以長條圖逐步播放泡沫、選擇、插入、希爾、合併、快速、堆積共 7 種排序，並可比較比較次數與寫入次數雜湊表計算工具以鏈結法、線性探測、二次探測、雙重雜湊顯示鍵放入雜湊表時的碰撞與儲存位置，並計算負載因子與平均探測次數時間複雜度（大O）比較工具以 O(log n)、O(n)、O(n log n)、O(n²)、O(2ⁿ) 等比較隨資料數而變的處理次數與時間，也能估算資料數改變時的處理時間

相關名詞

陣列 二分搜尋 二元堆積 穩定排序 中位數 雜湊表 鏈結串列 快取行 預取 二元搜尋樹

前往名詞解釋列表