簡明解釋算法中的大O符號

　　英文原文：What is a plain English explanation of Big O? With as little formal definition as possible and simple mathematics.

　　2009 年 1 月 28 日 Arec Barrwin 在 StackOverflow 上提問，“有沒有關于大O符號（Big O notation）的簡單解釋？盡量別用那么正式的定義，用盡可能簡單的數學來解釋”。在經過眾多熱心網友的修改更新后，最佳回復的得分已高達 3234 分，詳細內容，請見下文。

　　最佳回復所給出的大O符號的最簡單定義如下：

　　大O符號是一種算法復雜度的相對表示方式。

　　這個句子里有一些重要而嚴謹的用詞：

• 相對(relative)：你只能比較相同的事物。你不能把一個做算數乘法的算法和排序整數列表的算法進行比較。但是，比較 2 個算法所做的算術操作（一個做乘法，一個做加法）將會告訴你一些有意義的東西；
• 表示(representation)：大O(用它最簡單的形式)把算法間的比較簡化為了一個單一變量。這個 變量的選擇基于觀察或假設。例如，排序算法之間的對比通常是基于比較操作(比較 2 個結點來決定這 2 個結點的相對順序)。這里面就假設了比較操作的計算開銷很大。但是，如果比較操作的計算開銷不大，而交換操作的計算開銷很大，又會怎么樣呢？這就改變了先 前的比較方式；
• 復雜度(complexity)：如果排序 10,000 個元素花費了我 1 秒，那么排序 1 百萬個元素會花多少時間？在這個例子里，復雜度就是相對其他東西的度量結果。

　　在你閱讀了本文剩余部分后，再回來重讀上面的文字吧。

　　我所能想到的大O符號最好的例子就是做算術。拿兩個數字（123456 和 789012）舉例。我們在學校里學到的基本算術操作是：

• 加法；
• 減法；
• 乘法；
• 除法。

　　它們中每一個都是一次操作或一個問題。為它們求解的方法就被叫做算法（algorithm）。

　　加法是最簡單的了。你把加數排成行，按列加上每個數字，把所加得的數的末位數字寫到結果里。所加得的數的十位及其以上的數字轉入下一列的計算中。

　　讓我們假設在算法中，加上這些數是計算開銷最大的操作。合乎情理的說，為了把這兩個數加起來我們必須要加 6 次數字（并且可能進位到第 7 次）。如果我們把兩個 100 位數相加，我們必須做 100 次加法操作。如果我們把兩個 10,000 位數相加，我們必須做 10,000 次加法操作。

　　看到這里的模式了嗎？復雜度（complexity，就是操作的數量），對于加法中較大數的數字個數n，是直接成比例的。我們稱這為O(n)或者線性復雜度（linear complexity）。

　　除了借位替代了進位，減法也是相似的。

　　乘法就不同了。你把乘數排成行，取放在下面的乘數的第 1 個數字，把它逆序乘以上面乘數的每一個數字。下面乘數的其余數字也這樣做。所以為了乘我們的兩個 6 位數乘數，我們必須做 36 次乘法操作。我們還需要做 10 或 11 次列的加法操作來得到最終結果。

　　如果我們有兩個 100 位數相乘，我們需要做 10,000 次乘法操作和 200 次加法操作。兩個 100 萬位數相乘，我們需要做 1 萬億(10¹²)次乘法操作和 200 萬次加法操作。

　　作為n平方的算法衡量尺度，這就是O(n²)，即平方復雜度(quadratic complexity)。現在是時候介紹另一個重要概念了：

　　我們只關心復雜度最重要的部分。

　　敏銳的人可能已意識到，我們可以把操作次數表示為：n² + 2n。但正如你所看到的，我們的兩個 100 萬位數相乘的例子，第二個 2n 無關緊要（在那個階段，2n 只占操作總量的 0.0002%）。

　　有人注意到我們在這里假設場景為最壞的情況。當我們做 6 位數乘法時，如果其中一個是 4 位數另一個是 6 位數，那么我們只需做 24 次乘法操作。然而，對于那個’n'，我們仍然計算最壞情況，即乘數都是 6 位數的情況。因此，大O符號是關于一個算法的最壞情況的。

　　電話簿

　　我所能想到的下一個最棒的例子就是電話簿，通常叫做白頁電話簿或者其它類似名字，因國而異。但我要談論的是這種電話薄，這種電話薄把人按這樣的順序排列：姓、縮寫或名、地址、然后是電話號碼。

　　現在，如果你要指示計算機在一個包含1,000,000 個名字的電話簿中查找”John Smith”的電話號碼，你會怎么做？忽略也許你能猜測出S從電話簿哪里開始的事實（假設你不能猜測），你會怎么做？

　　一種典型的實現也許是，打開電話簿的正中間，取第 500,000 條記錄，把它和”Smith”進行比較。如果這恰好就是”Smith,John”，那我們真幸運。然而，”John Smith”更有可能在其前面或后面。如果在后面，那么我們把電話簿后面一半從中間劃分開，然后重復之前的過程；如果在前面，那么我們把第一半從中間劃分 開，然后重復之前的過程。以此類推。

　　這種算法叫做二分搜索(binary search)。不論你是否意識到，它在編程中每天都用到。

　　因此，如果你想要在包含 100 萬名字的電話簿中查找一個名字，事實上，通過這種算法，最多 20 次，你能找到任何名字。在比較搜索算法中，我們決定把比較操作作為我們的’n'。

• 對于有 3 個名字的電話簿，最多需 2 次比較。
• 對于有 7 個名字的電話簿，最多需 3 次比較。
• 對于有 15 個名字的電話簿，最多需 4 次比較。
• …
• 對于有1,000,000 個名字的電話簿，最多需 20 次比較。

　　這簡直好得難以置信，不是嗎？

　　用大O術語就是O(log n)，即對數復雜度（logarithmic complexity）。現在問題中的對數可以是 ln (底數為e)，log₁₀，log₂ 或者以其它為底數，這無關緊要，它仍然是O(log n)，正如O(2n²) 和 O (100n²) 都記為 O (n²)。

　　現在，值得花時間說明一下，對于算法，大O符號能夠被用于決定 3 種情況：

• 最好情況(Best Case)：在電話簿的搜索中，最好情況是我們比較了 1 次就找到了名字。這就是O(1)，即常數復雜度(constant complexity)；
• 期望情況(Expected Case)：正如上面討論過的，復雜度是O(log n)；
• 最壞情況(Worst Case)：也是O(log n)。

　　通常我們不關心最好情況。我們對期望和最壞情況感興趣。有時，期望情況更重要，有時最壞情況更重要。

　　回到電話簿的例子上來。

　　如果你有一個電話號碼，想要查找名字，要怎么做呢？警察有一個相反（按電話號碼排列）的電話簿，但是對于一般公眾，這樣的查詢會被拒絕，是吧？技術上，你能在普通電話簿中查找一個號碼。要怎么做呢？

　　你從第一個名字開始比較號碼。如果吻合，很棒，如果不吻合，你移到下一條記錄。你必須這樣做，因為電話簿是無序(unordered)的(電話號碼的排列是無序的)。

　　因此，查找一個名字：

• 最好情況(Best Case)：O(1);
• 期望情況(Expected Case)：O(n)（對應 500,000）;
• 最壞情況(Worst Case)：O(n)（對應1,000,000）。

　　旅行商問題

　　這是計算機科學中值得提到的一個相當有名的問題。在這個問題中，有N個城鎮，每個城鎮通過道路與 1 個或多個其它城鎮相連，道路的路程是確定的。旅行商問題就是找出訪問每個城鎮的最短路線。

　　聽起來很簡單？再想想。

　　如果有 3 個城鎮A、B、C，兩兩之間都有道路，那么你可以這樣走：

• A -> B -> C
• A -> C -> B
• B -> C -> A
• B -> A -> C
• C -> A -> B
• C -> B -> A

　　好吧，事實上，實際路線比上面的少，因為一些路線是等價的（例如，A -> B -> C 和 C -> B -> A 是等價的，因為它們使用同一條路線，只是方向相反）。

　　所以，事實上，這里有 3 條可能的路徑。

• 增加到 4 個城鎮，你有 12 條可能的路徑（如果我沒記錯）。
• 5 個城鎮，60 條可能的路徑。
• 6 個城鎮，360 條可能的路徑。

　　這是一個被叫做階乘(factorial)的數學運算函數。大體上：

• 5! = 5 * 4 * 3 * 2 * 1 = 120
• 6! = 6 * 5 * 4 * 3 * 2 * 1 = 720
• 7! = 7 * 6 * 5 * 4 * 3 * 2 * 1 = 5040
• …
• 25! = 25 * 24 * … * 2 * 1 = 15,511,210,043,330,985,984,000,000
• …
• 50! = 50 * 49 * … * 2 * 1 = 3.04140932 * 10⁶⁴

　　所以旅行商問題的大O符號表示是O(n!)，即階乘(factorial)或組合復雜度(combinatorial complexity)。

　　當你有 200 個城鎮的時候，使用傳統計算機，那么全世界已經沒有足夠的時間來解決這個問題了。

　　現在，有一些要思考的東西。

　　多項式時間

　　另一個我想要快速提及的要點是，任何復雜度為O(n^a)的算法被稱為有多項式復雜度(polynomial complexity)，或可以在多項式時間(polynomial time)內解決。

　　傳統計算機能解決可以在多項式時間內解決的難題。世界上有些東西就建立在這一基礎上。公鑰加密是個極好例子。找到一個很大的數的兩個素因子是困難的，如果不困難，那么我們就不能使用公鑰加密系統了。

　　總之，這就是我對大O符號的解釋（希望是清楚明白的英文解釋）。

　　翻譯： 伯樂在線 - 行云流水

　　譯文鏈接： http://blog.jobbole.com/55184/