數據結構和算法：算法復雜度

我們開始了算法復雜度的學習，本期教程我們學習后半段。

復雜度只考慮操作數目的一個數量級（忽略了其他的組分），這是一種近似。

為了表示這種近似，我們使用一個特定的符號，就是著名的  大 O 符號。

大 O 符號（Big O notation），又稱為漸進符號，是用于描述函數漸近行為的數學符號。更確切地說，它是用另一個（通常更簡單的）函數來描述一個函數數量級的漸近上界。在數學中，它一般用來刻畫被截斷的無窮級數尤其是漸近級數的剩余項。在計算機科學中，它在分析算法復雜度的方面非常有用。大 O 符號是由德國數論學家 保羅·巴赫曼（Paul Bachmann）在其 1892 年的著作《解析數論》（Analytische Zahlentheorie）首先引入的。而這個記號則是在另一位德國數論學家 艾德蒙·朗道（Edmund Landau）的著作中才推廣的，因此它有時又稱為 朗道符號（Landau Notation）。代表“order of …”（…階）的大 O，最初是一個大寫希臘字母“Ο”（Omicron），現今用的是大寫拉丁字母“O”。

例如，小鴨子們去度假這個故事里，農夫 Oscar 的第一種算法有 N2 個操作，我們就說此算法的復雜度是 O(N2)。類似地，第二種更快的算法的復雜度是 O(N)。

大 O 符號有點像一個大圓形的袋子，可以把不同的操作數目整合在一起，使之具有一個同樣的數量級。

例如，如果有三個算法，它們的操作數目分別為 N，5N + 7 和 N / 4，我們就都用 O(N) （讀作 “N 的 大 O”。當然了，讀法其實不是那么固定）來表示這三個算法的復雜度。

類似地，如果一個算法的操作數是（2 * N2 + 5 * N + 7），那么它的復雜度是 O(N2)：我們忽略了 5 * N 和 7 這兩項，因為它們與 2N2 相比數量級較小。隨著 N 的增大，這兩項的增長速率比 2N2 要慢，因此我們保留 2N2 即可，又因為常數乘法因子（這里是 2）不予考慮，因此記為 O(N2)。

我們說 f(N) 表示“N 的函數”（例如， f(N) = 2 * N2 + 5 * N + 7) ），那么 O(f(N)) 表示的是“大約有 f(N) 個操作的算法的復雜度”，這里的“大約”是非常關鍵的。

2. 時間復雜度和空間復雜度

下面我們來學習算法中常聽到的“時間復雜度”和“空間復雜度”。

為什么我竟然想到了漫威里面的大反派滅霸的無限手套呢？上面有時間寶石和空間寶石這兩顆無限寶石。一定是因為我看了《復仇者聯盟3：無限戰爭》和《復仇者聯盟4：終局之戰》的關系…

那么“時間復雜度”和“空間復雜度”這一對“活寶”到底是啥意思呢？且聽我慢慢道來。

“在很久很久以前，宇宙中有 6 顆無限寶石，分別是時間寶石、空間寶石…”

為了盡可能精確地表達算法的復雜度，我們可以做很多選擇。

首先，我們選擇輸入條件的量化，例如通過變量 N（N 行 N 列小鴨子，N 個學生，N 架飛機，等）。當然了，不一定要用 N 這個變量名，我們可以選擇其他變量名（比如 M，Z，X，Y 等），但更重要的是我們也可以不止用一個變量。

例如，如果我們的問題是要在一張紙上畫畫，那么我們可能會將算法的復雜度表達為畫紙的長度 L 和寬度 W 的函數。同樣地，如果農夫 Oscar 擁有比可用的池塘數目更多的小鴨子的行數，那么他可以將算法的復雜度表達為小鴨子的行數 N 和池塘數 P 的函數。

另一個重要的選擇是要度量的操作的類型。到目前為止，我們其實只談論了算法的效率或性能（就是算法快不快）。但是，程序員不僅對算法的執行時間感興趣，他們也可能會度量許多其他特性，最常見的是內存消耗（Memory Consumption）。

算法的內存消耗也是度量算法復雜度的標準。例如，如果需要為一個輸入大小為 N 的算法分配 N 千字節（KiloByte，千字節，簡稱 KB。其實是 1024 個字節）的內存，則此算法的內存復雜度可以表示為 O(N)。

內存復雜度是和算法的內存消耗有關的復雜度，度量的并不是算法的效率，而是消耗/占用的內存空間大小，因此我們把它稱為算法的空間復雜度（Space Complexity）。相對的，之前我們討論的對于算法的執行速度（快不快）的度量是用的時間復雜度（Time Complexity）。

空間復雜度是對一個算法在運行過程中臨時占用存儲空間大小的度量，記做 S(N) = O(f(N))。相對的，算法的時間復雜度就記為 T(N) = O(f(N))。因為 S 是 Space（空間）的首字母，T 是 Time（時間）的首字母。

在計算算法的空間復雜度的時候，我們其實也不知道算法所消耗/占用的具體的內存大小（內存是以字節（Byte）為單位），我們計算的是算法所使用的（數據）結構的數量級。

比如說你使用 N 個大小為 N 的數組，那么其空間復雜度為 O(N2)。

例如，對于小鴨子們去度假的那個故事，可能農夫 Oscar 給他的每只小鴨子都起了一個英文名字。他隨身攜帶著一份小鴨子的名字的表單，以免自己忘記。

上面的表格是農夫 Oscar 用來記錄小鴨子們的名字的表單的一個直觀的表示：一共有 5 個名字（HARRY，JAMES，HENRY，EMILY，ALICE），分別對應 5 只小鴨子。表格里的每一行儲存一個名字，每一行有 5 個格子（類似于數組的 5 個元素），5 x 5 = 25 個格子，一個格子里是一個英文字符。

如果聯系到計算機的內存層面，N 只小鴨子需要 N 個數組來保存它們的名字，每個數組里是一只小鴨子的名字（都是英文字符），而數組的大小（這里是字符數）都統一為 N。所以這里的空間復雜度為 O(N2)。

有些時候，我們需要同時考慮算法的時間復雜度（執行速度）和空間復雜度（執行期間占用的內存空間的大小）。

一般在比較簡單的情況下，我們對算法的空間復雜度沒有那么關注。但對于更復雜的問題，算法的空間復雜度也許會引起更多的重視：例如，我們也許會通過犧牲一點執行速度來使用更少的內存；或者甚至通過增加算法的空間復雜度來提高執行速度，例如通過在表中存儲已經計算好的結果（緩存（cache）的原理）。

對程序的約束越多，所需的信息就越精確。在計算機科學的某些領域，我們也會對算法的其他特征感興趣。而這些特征中的某些也可以用算法的某種復雜度來度量。例如，大型計算機或嵌入式系統的程序員可能會考慮算法的功耗，以節省電量。

然而，在一般情況下，我們只關注算法的時間復雜度和空間復雜度，甚至主要關注時間復雜度。

3. 最壞情況下的復雜度

正如我們之前所說，算法執行的操作數目很明顯取決于起始條件。

例如，下面是一個非常簡單的算法，用于獲知一個給定的值是否在值列表中（例如，“我是否已將雞蛋加入我的購物清單？”）：

為了獲知一個給定的值是否在值列表中，我們可以這么做：

遍歷整個列表，在找到給定值的時候即可停下，表示值在列表中；

如果我們已經遍歷完整個列表，仍然沒有找到給定值，那么說明給定的值不在值列表中。

想象一下，如果我們要查找的值不在列表中，并且列表里有 L 個元素。那么要確定這個值是否存在，算法就必須遍歷一遍整個列表，將每個值與要查找的值進行比較，那將需要進行 L 次比較。因此，我們可以說算法具有 O(L) 的復雜度（很明顯，這里考慮的是時間復雜度）。我們也可以說，此算法的時間復雜度是呈線性的（如果我們將輸入列表的大小加倍，那么此算法將花費兩倍的時間）。

但是，如果要查找的值位于列表的最開頭，會怎么樣呢？

例如，如果“雞蛋”是我們的購物清單中的第一個元素，它會立即被注意到，我們將僅在進行一次操作后就停止遍歷。在其他情況下，即使列表包含 3000 個元素，可能我們的搜索工作也會在 4 到 5 次操作后停止。

這就是 “最壞情況”（Worst Case）的概念發揮作用的地方：在計算算法的復雜度時，可以認為給定的輸入對于我們的算法來說是處于“最壞的情況”。我們將計算需要最多操作（而不僅僅是一個或兩個）的輸入情況下的操作數，例如給定值不在列表里的情況。

從程序員的角度來看，這是一種安全性：計算出的復雜度處于“最壞情況”，因此他知道算法的表現只會更好。

就像網絡安全領域的程序員會通過自問“最心懷惡意的用戶可能會通過輸入什么文本來入侵我的網站？”這樣的問題來敦促自己提升應用程序的安全性一樣，專注于算法研究的人也想知道“到底是算法中的哪個元素花了我的算法的大部分時間？”

這種方法可以度量所謂的“最壞情況下的復雜度”。