2 min read

算法複雜度筆記

Table of Contents

資源

  • 時間:需要經過多少步演算才能解決問題
  • 空間:解決問題時需要多少記憶體

時間和空間是最重要的兩項資源。

以時間 T 為例,如果輸入的資料長度 n 作為變數,我們關注的是時間與資料之間的函數關係 T(n) ,同一算法在不同計算模型實現時可能會有常數因子的差別,因此我們使用 Big O 表達式來表示 T(n),可以忽略常數因子。

Big O

Big O 又可稱為 Landau symbol,最初是大寫的希臘字母 Θ(Omicron),現在用的是英文大寫 O,用來表達「無窮大漸進」。

比如說,解決規模為 n 的問題所需要的時間為 $ T(n) = n^2 + n + 2 $,當 n 逐漸增加,其他各項的影響可以忽略,因此 Big O 表達式可以記為 $ T(n) ∈ O(n^2) $,或是 $ T(n) = O(n^2) $,我們可以說此算法有 $ n^2 $ 的時間複雜度。

此外,Big O 也可以用來描述誤差(無窮小漸進),例如泰勒展開式 $ e^x = 1 + x + {x^2 \over 2} + O(x^3) $,當 x 趨近於 0,誤差的絕對值小於 $ x^3 $ 的某一常數倍。

常數時間 $ O(1) $

所需時間與資料大小無關,例如存取陣列中的單個元素。

對數時間 $ O(\log n) $

由於電腦以 2 進位,對數經常以 2 為底,例如二分搜尋法。

線性時間 $ O(n) $

所需時間與輸入資料的大小成正比,某些數學認為無法在標準計算模型下達到線性時間的算法,可以利用平行運算架構來達成。

須依賴全部輸入內容才能得解的問題,它最少也得要線性時間才能得解,因為它至少得花線性時間來讀取資料。

線性對數時間 $ O(n\log n) $

多項式時間 $ O(n^m) $

傳統計算機只能解決多項式時間內的難題,有些密碼學原理便是依此發展,例如非對稱加密(公開金鑰加密法),就是利用對大數作質因數分解的時間複雜度,提供加密內容可靠的保護。

延伸資料可以參考P/NP問題。

指數時間 $ O(m^n) $

所需時間隨著資料大小呈指數成長。

階乘時間 $ O(n!) $

例如旅行推銷員問題,假設有 n 個城鎮,推銷員希望找出「可以通過每個城鎮的最短旅行路徑」,要找出來,必須窮舉所有可能的路線:

n可能性所需時間
33$ {2 \times 3} \over 2 $
412$ {2 \times 3 \times 4} \over 2 $
560$ {2 \times 3 \times 5 \times 5} \over 2 $
6360$ {2 \times 3 \times 4 \times 5 \times 6} \over 2 $

參考資料