演算法複雜度分析（一）

02-01

之前由於高考等原因，專欄好幾個月沒更新了，在此說聲抱歉。

請允許我我先吐槽一下知乎的辣雞編輯器，剛才我在 Chrome 上寫，打出來的文字順序居然都是亂的，換到 Edge 上好一點……知乎工程師如果就這樣的話，這網站真是??……

計算複雜度

解決一個問題有不同的演算法，比如之前幾篇文章寫的排序演算法。而不同的演算法處理問題需要的資源又有不同。我們將演算法需要的資源稱為演算法的複雜度。演算法的複雜度包括時間複雜度和空間複雜度。

由於空間資源可以很輕易的獲得（買硬體），所以我們很少考慮空間複雜度的問題（但是也不能太浪費了）而主要考慮時間複雜度。

在數據量較小時，不同演算法的時間複雜度的差異表現得並不明顯。但是，在處理大量數據（大數據時代，數據量可是動不動就上億）時，演算法之間的差異就很明顯了。仍然用排序舉例，對於一億個數，如果用冒泡排序，要用近一億億個單位時間（取決於硬體）；如果用歸併排序，只用近二十七億（估算）個單位時間就可以搞定。

通常表示數據規模和時間的函數是很複雜的，絕非簡單的 n^2 等。但是，一般情況下我們不需要精確地得出這個這個函數，得到它的量級就夠了。我們將複雜度的量級稱為漸進複雜度，簡稱複雜度（精確的複雜度真的很少用）。在漸進複雜度中，我們忽略了常數項和增長速度較小的項。

為了描述漸進複雜度，我們引入了三種記號，分別是 $O$ ， $Omega$ 和 $Theta$ 。在下面為了輸入方便，我將直接輸入為 O ， Omega 和 Theta 。

最常用來描述漸進複雜度（即評估函數增長速率）的表示法是由 Paul Bachmann 於 1894 年引入的大 O 表示法。給定兩個正值函數 f 和 g ，有如下定義：

如果存在正數 c 和 N ，對於所有的 n >= N，有 f(n) <= c * g(n) ，則 f(n) = O(g(n))。

上述定義可以理解為 g(n) 是 f(n) 的一個上界，也可理解為 f 至多與 g 增長得一樣快。

但是根據定義，我們可以發現對於任意給定的 f 和 g ，存在無數對正數 c 和 N 滿足條件。同時，對於一個 f ，會有無數個 g 滿足條件。例如：

f(n) = 2 * n ^ 2 + 3 * n + 1 = O(n ^ 2) = O(n ^ 3) = O(n ^ 3.5) = ...

為了避免這種情況，我們一般取最小的 g 函數。在此例中即為 n ^ 2 。

大 O 表示法具有以下性質：

性質 1 （傳遞性）：如果 f(n) = O(g(n)) ，g(n) = O(h(n))，則 f(n) = O(h(n)) 。（定義）

性質 2 ：若 f(n) = O(h(n)) ，g(n) = O(h(n)) ，則 f(n) + g(n) = O(h(n)) 。（定義）

性質 3 ：a * n ^ k = O(n^k) 。（定義）

性質 4 ：對於任何 j > 0 ，n ^ k = O(n ^ (k + j)) 。（定義）

性質 5 ：如果 f(n) = c * g(n)，則 f(n) = O(g(n)) 。（定義）

性質 6 ：對於任意正數 a 和 b (a, b ≠ 1)， $log_{a}n=O(log_{b}n)$ 。（換底公式）

以上性質證明均略去，有興趣的讀者可以結合括弧內的提示自己證明。

通過定義和以上四條性質，我們可以得出以下結論：

任何多項式都是該多項式中最高次項的大 O 表示。即：

$f(n) = sumlimits_{i=0}^{k}a_{i}n^i = O(n^k)$

大 O 表示法表示函數的上界。與之對應的存在下界的表示：

給定兩個正值函數 f 和 g ，如果存在正數 c 和 N ，對於所有的 n >= N，有 f(n) >= c * g(n) ，則 f(n) = Omega(g(n))。

定義表明 c*g(n) 是 f(n) 的下界，f 至少以 g 的速率增長。

大 O 表示法和 Omega 表示法可以相互轉化：

g(n) = O(f(n)) 等價於 f(n) = Omega(g(n))

Omega 表示法與大 O 表示法有類似的問題。我們一般取最大的 g 進行表示。

給定兩個正值函數 f 和 g ，若存在正數 c1 、c2 和 N ，對於所有 n >= N ，有 c1 * g(n) <= f(n) <= c2 * g(n) ，則 f(n) = Theta(g(n)) 。

定義表明 f 與 n 同階，增長速率大致相同。

我們在大 O 表示法和 Omega 表示法中忽略了常數係數，但是常數係數也可能對演算法效率產生巨大的影響。

讓我們假設某個問題有兩個演算法，需要的操作次數（指令條數）分別為 10 ^ 8 * n 和 10 * n ^ 2。如果只看漸進複雜度，第二個演算法會被淘汰掉。但是如果數據規模 n < 10 ^ 7 ，第二個演算法需要的時間是要少於第一種演算法的。