大數據文摘出品
來源：medium
編譯：劉佳瑋、李雷、陸震、高延、張秋玥、王緣緣、fuma、錢天培
啥是算法？
算法就是，程序猿懶得給你解釋代碼時，堵你嘴的東西。（這一步使用了XX算法。）
開個玩笑！不論什麼算法，寫出來之後你都得對它負責。
提到算法，就不得不提到複雜度分析——這也是程序猿面試跑不了的一關。
「複雜度分析」，說起來概念特別簡單，可真分析起來，又常常讓人手足無措。
今天，文摘菌就引用一些神奇寶貝的例子，給大家溫故一下複雜度分析的概念，然後從易到難給大家介紹複雜度分析的常用方法。
文章分為5個部分。
1. 為什麼要做「複雜度分析「？
2. 如何做「複雜度分析「？
3. 從排序算法說起
4. 遞歸算法分析
5. 如何選擇最好的算法？
其中，1、2部分會對複雜度分析做簡單介紹（熟悉複雜度分析基本概念的同學可以跳直部分3）。部分3會以排序算法為例，給出複雜度分析的經典案例。 部分4會重點分析遞歸算法，並介紹遞歸算法複雜度分析的兩種方法：「遞歸樹法」和更通用簡潔的「主定理法」。最後，部分5會簡要討論，在實際情況中我們如何根據複雜度分析選擇最好的算法。
為什麼要做「複雜度分析」？
舉個慄子來解釋。
我們假設可愛的神奇寶貝們設立了一場錦標賽。每場比賽都有兩個神奇寶貝參賽，勝者的等級會得到提升。
每次比賽，我們都會隨意選出一個神奇寶貝，然後選出和它等級最接近的一位作為它的對手。
很簡單嘛！在選取第一位神奇寶貝後，你可以將它的等級和其他所有神奇寶貝比較，這基本上是線性搜索。
但在比賽當天，我們假設有1000個口袋妖怪報名比賽！這個算法還可行嗎？
可擴展性：繞也繞不過的問題
由上面的簡單例子可見，可擴展性往往是是算法性能中不得不考慮的重要一環。
如何評估算法的可拓展性，我們就要講到漸進分析。（通常，複雜度分析也就是我們這講的漸進分析）
漸近分析是僅根據輸入大小（N）來評估算法的性能，其中N可以非常大。漸進分析可以讓你了解應用程式的局限性，因此對于衡量代碼的性能非常重要。
例如，如果參與戰鬥的小寵物的數量是N，那麼線性搜索算法的漸近複雜度是O（N）。如果你不知道這個符號是什麼，請不要擔心。我們馬上就告訴你。
簡單來說，你要詢問N個小寵物他們的等級是什麼，然後做出決定。想像一下，問所有1000個小寵物，這絕對是個累人的工作！
對於一臺機器來說，O（N）可能並不壞，但對於一個看重響應速度和處理速度的網站而言，它可能不是最好的選擇。
不考慮輸入巨大的情況，你早晚會遇到可拓展性問題。
回到上面的例子。如果我們使用字典，或哈希表來查找具有相同排名的所有小寵物，我們就可以將算法時間複雜度降低到O（1）。
這就號像我們有個知曉所有神奇寶貝等級的經理人。我們只要問一下他，就能知道匹配答案了！
如何做「複雜度分析」？
讓我們再來舉一個漸進分析的例子吧！
我們假設皮卡丘正在尋找一個具有某種特殊能力的合作小精靈。皮卡丘開始逐一向所有小寵物詢問他們的能力。這種方法被稱為線性搜索，因為它是逐個線性地完成的。但是為了方便參考，讓我們稱之為「皮卡丘搜索」。
在上面的代碼片段中，pokemons_list是參與錦標賽的所有神奇寶貝的列表。因此，該列表的大小為N。
皮卡丘搜索的運行時間分析：
1.第2步是一個循環，因此，其中的操作將重複N次。僅當步驟3中的條件為真時才執行步驟4。執行步驟4後，循環中斷並返回結果。
2.如果步驟3花費的時間是常數級的，比如C1，那麼for循環所用的總時間將是C1×N。
3.所有其他操作都是不受循環影響的常數時間操作，因此我們可以將所有這些操作作為C2的累計常量。
總運行時間f(N)=C1×N+C2，是一個與N相關的函數。
讓我們把N放大。如果N的值非常非常大，該怎麼辦？你認為常數會有什麼意義嗎？
注意！在算法分析中，一個重要的想法是，忽略不太重要的部分。
例如，如果算法的運行時間漸近表示為10N?+ 2N + 5，則只有高階項N?才有意義。這使得算法之間的比較更容易。
不同情況下的分析
每當輸入不同，算法呈現的效果也不同。這意味著，我們需要討論如何定義這種行為或算法的複雜性。
1.最佳情況?絕對樂觀。皮卡丘非常幸運，因為他接觸的第一個精靈就擁有他正在尋找的特殊能力。
2.最差情況?絕對悲觀。皮卡丘不得不去拜訪所有的小精靈，更令他沮喪的是，最後一個才擁有他想要的超能力。
3.普遍（平均）情況?實事求是。皮卡丘現在已經長大，並且很有經驗，他知道這一切都是時間和運氣的問題。他估計在他遇到的前500個左右的精靈中找到超級口袋精靈的機會很高，他是對的。
上述三種情況都可以被用來分析算法。
「最佳情況複雜度」沒有太大用處。它可以作為算法複雜度的下限值。如果你執意要用它來表示算法複雜度，那麼你就只考慮了最佳情況。你必須得非常幸運，這樣你的算法才能達到最佳情況。從實際意義上說，這對算法沒有多大幫助。
「平均情況複雜度」通常很難計算，因為它需要你分析算法在各種輸入上的性能，因此也沒有被廣泛的使用。
「最差情況複雜度」幫助你做好最壞的準備。在算法中，這種悲觀主義是好的，因為它給出了複雜度的上限，這樣你就知道你的算法有哪些限制！
複雜度分析工具
前面我們看到，皮卡丘搜索其他小精靈的總運行時間是N的函數，f(N)= C1.N + C2。讓我們來了解一下有哪些工具可以用來表示運行時間，以便比較各算法。
Big O ：哦，沒錯！它的發音就是這樣，Big?—?Oh ！它是算法複雜度的上限。因此，它用於表示算法的最差情況。
它實際的意思是，不管輸入是什麼，算法的最大運行時間是多少。
這是使用最廣泛的表達，因為它可以通過最差情況來分析算法。
C是常量。f（N）是運行時間函數，上界為g（N）。
對於皮卡丘的搜索，我們可以說f（N）或運行時間對於非常大的N，會向上達到C.g(N)，其中c是一個常量，g(N) = N。因此，O(N)表示皮卡丘搜索的漸近上界。
Big Omega（Ω）：與Big O表示法類似，Ω表示法用於定義算法性能的漸近下界。因此，它用於表示最佳情況場景。
Ω 下界本質上是在不考慮輸入的情況下，算法執行所需的最短時間。
在實際情況中，這種表示法並不常用，因為研究最佳情況不能成為算法比較的正確衡量標準。
C是常量。f（N）是運行時間函數，其下界是g（N）。
對於皮卡丘的搜索，我們可以說f（N）或運行時間對於非常大的N，會向下達到C.g(N)，其中c為常量，g(N) = 1。因此Ω(1) 表示皮卡丘搜索的漸近下界。
Big Theta（Θ）：算法行為的嚴格約束，此符號定義函數的上界和下界。這稱為緊確界，因為我們將運行時間限制在上下兩個常量因子內。就像這樣：
C1和C2是常量。f（N）是運行時間函數，g（N）是緊確界
每個算法可能有不同的最佳和最差情況。當兩者相同時，我們傾向於使用Θ表示法。否則，最佳和最差情況需要被分別表示：
（a）對於很大的N值，最差情況的 f（N）受函數g(N) = N的限制。因此，緊確界複雜度將表示為Θ(N)。這意味著最壞的情況下皮卡丘的搜索時間是最少要C1?N，最多要C2?N。
（b）類似地，其最佳情況的緊確界複雜度是Θ(1)。
空間複雜度
我們之前一直在討論時間複雜度。複雜度分析中的另一個重要概念是空間複雜度。顧名思義，它是指算法在N非常大的情況下佔用多少硬碟空間或內存。
每當我們比較用於解決特定問題的各算法時，我們不僅僅關注時間複雜度，空間複雜度也是比較不同算法的重要方面。是的，可能目前我們的機器有大量可用內存，因此，多消耗些空間沒什麼影響。但是，我們不應該一直忽視它。
時空權衡
通常，你希望你的算法速度要快，而這樣做可能最終會導致很糟糕的空間複雜度。
但有時，我們會犧牲一些時間來換取空間的優化。
在實際應用中，犧牲時間或者空間以換取另一方的優化被稱為算法分析領域的「時空權衡」。
皮卡丘現在意識到了，他每隔一天就要尋找一個神奇寶貝。這意味著一遍又一遍地運行皮卡丘的搜索。嗯！他肯定厭倦了每天的大量重複工作。
為了幫助他加快搜索過程，我們決定使用哈希表。我們可以使用神奇寶貝的能力類型作為哈希表的鍵值。
如果我們需要找到具有某種特殊能力的小精靈，最壞的情況就是複雜度為O(1)，此時哈希表的查找時間是一個恆定值。
所以現在所需要的只是創建一個哈希表，然後使用它進行查找以降低整體運行時間！
但事情也不是這麼簡單，你可以看到這麼做帶來了空間成本。哈希表對每個Pokemon精靈會用一個條目來存儲。因此，空間複雜度是O(N)。
選時間O(N) 空間O(1) ？還是時間O(1) 空間O(N)呢？
這樣的選擇取決於實際應用的需要。
如果我們有一個面向客戶的應用程式，它的響應速度就不應該很慢。在這種情況下，優先考慮的是，無論使用多少空間，應用程式都應儘可能快速響應。但是，如果我們的程序受到可用空間的限制，則必須放棄快速響應來彌補空間的緊缺。
從排序算法說起
時間和空間的複雜性始終是緊密相連的。我們需要進行數學運算並且採用最好的方法。
現在，我們就來進行一些正兒八經的複雜度分析啦！
首先，皮卡丘想分析所有的排序算法。
讓我們看看基本但關鍵的排序算法。假設要排序的輸入數組pk_rank的大小為N.
如果你不熟悉下面提到的任何一種排序算法，建議你在閱讀後面部分之前先了解一下它們。以下示例的目的不是為了解釋不同的算法，而是去解釋如何分析它們的時間和空間複雜度。
冒泡排序
冒泡排序是最簡單的排序算法之一，它反覆比較數組的相鄰元素，如果它們亂序則交換位置。可以類比水裡的泡沫最後會上升到水面上。隨著數組元素的排序，它們會逐漸冒泡到數組中的正確位置。
就像皮卡丘玻璃杯中的氣泡。
冒泡排序算法
時間複雜性：現在我們已經有了算法，再來分析它的時間和空間複雜性。我們可以清楚地從步驟2和3中看到算法中存在嵌套循環結構。第二個for循環的範圍是N-1-i，表明它依賴於上一個循環。
當 i = 0時, 第二個for循環會被執行N-1次
當 i = 1時, 第二個for循環會被執行N-2次
當 i = 2時, 第二個for循環會被執行N-3次
當 i = N-1時, 第二個for循環會被執行0次
現在我們知道了冒泡排序算法在整個過程中的每一步所花費的時間。我們之前提到過，算法中有一個嵌套循環。對於第一個循環中的每個變量值，我們知道在第二個循環中所花費的時間。現在剩下的就是給這些加和。我們這樣做：
S = N-1 + N-2 + N-3 + ... + 3 + 2 + 1
~ N * (N+1) / 2
~ N? + N（忽略常數）
如果你查看步驟4和步驟5，這些是常量時間操作。它們並沒有真正增加時間複雜度（或者空間複雜性）。這意味著，我們有N?+ N次迭代，並且在每次迭代中，我們都執行了這些常量時間操作。
因此，冒泡排序算法的運行時間複雜度為C.（N?+ N），其中C是常量。因而我們可以說冒泡排序的最壞情況是時間複雜度為O（N?）。
這是一個很好的排序算法嗎？我們還沒有看過任何其他類似的算法來進行比較。但是，讓我們看看這個算法需要多長時間來排序十億個皮卡丘。
我們將計算留給你，結果是：排序十億個皮卡丘（假設每個指令需要1毫秒執行）將需要大約31，790年。
空間複雜性：與該算法的時間複雜度相比，分析空間複雜度相對簡單些。冒泡排序算法僅僅重複執行一個操作--交換數字。同時，它不使用任何外部存儲器。它只是重新排列原始數組中的數字，因此，空間複雜度是個常量，即O（1）或者Θ（1）。
插入排序
你喜歡打牌嗎？
在抓牌時，我們往往需要對牌組進行排序。插入排序的思想非常類似於對牌組進行排序。
比方說，你有幾張按升序排序的卡牌。如果你被要求在右邊插入另一張牌，同時要保證你手中的牌仍然是有序的。你會怎麼做？
你可以從手中牌的最左側或最右側開始，將新牌與每張牌進行比較，從而找到合適的位置。
找到合適的位置後，你就可以在那裡插入新抓的牌。
同樣，如果有更多新牌，則對每張新卡重複相同的過程，同時要保證手中的卡是有序的。
插入排序原理相同。它從索引1開始（數組排序從0開始）並將每個元素視為一張新卡。然後，每個新元素就可以放置在已經排序的子陣列中的正確位置。
這裡需要注意的重要事項是，給定一張新牌（即我們例子中索引為j的一個元素），手中的所有卡（即該索引前的所有元素）都已經排序完畢。
讓我們看一下插入排序的正式算法。
時間複雜度：從步驟1和4開始，在for循環中有一個嵌套的while結構。 while循環運行j + 1次，其中j依賴於i。讓我們看看j的值如何隨著i的變化而變化。
當i=1時，j=0，while循環會被執行1次。
當i=2時，j=1，while循環會被執行2次。
當i=3時，j=2，while循環會被執行3次。
當i=N-1時，j=N-2，while循環會被執行N-1次。
現在我們知道插入排序算法在整個過程中的每一步所花費的時間（即迭代）。總時間是：
S = 1 + 2 + 3 + … N-2 + N-1
~ N * (N+1) / 2
~ N? + N（忽略常數）
步驟2到7是常量時間操作。它們並沒有真正增加時間複雜度（或者空間複雜性）。這意味著，我們有N?+ N次迭代，並且在每次迭代中，我們都執行了這些常量時間操作。
因此，插入排序算法的運行時間複雜度是C.（N^2 + N），其中C是常量。因此，我們可以說插入排序的最壞情況是時間複雜度與冒泡排序的時間複雜度即O（N^2）相同。
空間複雜性：與該算法的時間複雜度相比，分析空間複雜度相對簡單些。插入排序算法僅重新排列原始數組中的數字。同時，它根本不使用任何外部存儲器。因此，空間複雜度是常量，即O（1）或者Θ（1）。
注意：基於漸近複雜度比較算法簡單快捷。從理論分析來看，它是一個很好的衡量標準。但是從實踐層面上看，如果兩種算法具有相同的複雜性，也不一定意味著它們在實際場景中具有相同的表現性能。
在計算算法的漸近複雜度時，我們忽略所有常量因子和低階項。
但是這些被忽略的值最終會增加算法的運行時間。
當數組幾乎已經是按順序排列好的時候，插入排序比冒泡排序快得多。對於每次遍歷數組，冒泡排序必須一直走到數組的末尾並比較相鄰數字的大小；另一方面，如果數組其實已經被排序，插入排序則會提前終止。你可以嘗試在一個已經被排序的數組上執行這兩個算法，並查看每個算法完成執行所需的迭代次數。
因此，當你在為自己的應用程式尋找最佳算法時，總是需要從許多不同方面進行分析。漸近分析肯定有助於淘汰較慢的算法，但更多的觀察和更深入的見解有助於為你的應用找到最適合的算法。
合併排序
到目前為止，我們已經分析了兩種最基本的排序算法。這些排序算法算是入門級必須介紹的，但它們具有高漸近複雜性，因此通常在實踐中我們並不使用他們。
讓我們來看一看更快、更實用的排序算法吧。
合併排序算法摒棄了我們在前兩個算法中看到的嵌套循環結構化排序，採用了我們將在下面討論的全新範例。
合併排序算法基於一種被稱為各個擊破的編程範式。這種編程範例基於一個非常簡單的想法，並且在許多不同的算法中都很實用——包括合併排序。各個擊破分為三個基本步驟：
劃分：將一個大問題分解為更小的子問題。
攻克：最佳地解決子問題。
合併：最後，結合子問題的結果，找到原始大問題的解決方案。
讓我們看一下合併排序算法是如何利用各個擊破方法來解決問題的。
1.劃分：該方法中的第一步是將給定的數組劃分成兩個大小相等的較小子數組。這其實還是挺有用的，因為我們現在只需要對兩個只有原來元素數量一半的數組進行排序啦。
2.攻克：下一步是對較小的數組進行排序。這部分被稱為攻克步驟，因為我們正在試圖以最佳方式解決子問題。
3.結合：最後，我們看到原始數組的兩半，他們都被排序好啦。現在我們必須以最佳方式來組合它們，以得到一整個排序好的數組。這其實是上面幾步的組合步驟。
可是等等。這樣就完了嗎？
給定一個包含1000個元素的數組，如果我們將它分成2個相等的一半，每個500，我們仍然有很多元素要在數組（或子數組）中進行排序。
我們不應該將這兩半進一步劃分為4，以獲得更短的子陣列嗎？
當然應該啦！
我們遞歸地將數組劃分為較小的數組們，並對它們進行排序與合併以重新獲得原始數組。
這實質上意味著我們將例如1000的數組分成兩半，每組500。然後我們進一步將這兩半分成4個部分，每部分250個，依此類推。如果你無法在複雜性分析方面直觀地考慮所有這些問題，請不要擔心。我們很快就會談到這一點。
我們來看看合併排序算法。該算法分為兩個函數，一個遞歸函數對給定數組的兩半分別進行排序，另一個則將兩半合併在一起。
我們將首先分析合併（merge）函數的複雜性，然後分析合併排序（merge_sort）函數。
合併兩個排好序的數組
上面的函數簡單地將數組的兩個已排序的一半合併為一個已排序的數組。用索引來表示兩半的話就是，左半部分來自[left, mid]，右半部分來自[mid + 1, right]。
第2-3步將元素從原始數組複製到臨時緩衝區，我們使用此緩衝區進行合併。已排序的元素將被複製回原始數組。由於我們會遍歷數組的某個部分，假設該數組有N個元素的話，該操作的時間複雜度為O(N)。
第5步是一個while循環，迭代兩個子數組中較短的一個。這個while循環和之後第13與14步內的循環涵蓋了兩個子陣列的所有元素。因此，他們的時間複雜度是O(N)。
這意味著合併步驟算法的時間複雜度是線性的。
合併排序的總體複雜性取決於調用合併函數的次數。
讓我們繼續看看原始的合併排序（merge_sort）函數。
第4步在數組的左半部分調用該函數（merge_sort）。
第5步在數組的右半部分調用該函數（merge_sort）。
然後第6步最後調用合併（merge）函數將兩半結合起來。
呃。一個函數調用自己？
如何計算它的複雜性？
目前為止我們已經討論過循環分析。然而，許多算法（比如合併排序）本質上是遞歸的。當我們分析它們時，我們得到時間複雜度上的遞歸關係。我們獲得了計算輸入大小為N的算法時間複雜度的函數；它依賴於N，以及小於N的輸入的運行時間。
遞歸算法分析
主要有兩種方法來分析遞歸關係的複雜性：
1.使用遞歸樹
2.主定理方法
遞歸樹分析
這是分析遞歸關係複雜性最直觀的方式。本質上，我們可以以遞歸樹的形式可視化遞歸關係。
可視化有助於了解算法在每個步驟（讀取級別）完成的工作量。總結在每個級別完成的工作能夠告訴我們算法的整體複雜性。
在我們畫出合併排序算法的遞歸樹之前，讓我們首先看一下它的遞歸關係。
T（N）= 2T（N / 2）+ O（N）
用T(N)表示對由N元素組成的數組進行排序所完成的工作量（或所花費的時間）。上述關係表明，所花費的總時間等於將數組的兩半分別排序所花費的時間加上將其合併所花費的時間。我們已經知道合併兩半數組所花費的時間了——O(N)。
我們可以寫出遞歸關係如下：
T（N） = 2T（N / 2）+ O（N）
T（N / 2）= 2T（N / 4）+ O（N / 2）
T（N / 4）= 2T（N / 8）+ O（N / 4）
......
以樹的形式可視化更容易。樹中的每個節點都包含兩個分支，因為在給定每個單個問題時我們都有兩個不同的子問題。讓我們看一下合併排序的遞歸樹。
用於歸併排序的遞歸樹
每一個節點表示一個子問題，每個節點上的數值表示解決該問題需要花費的工作量。根節點表示的就是初始問題。
在我們的遞歸樹中，每個非葉節點有2個子節點，而且標有子所劃分處的子問題數量。從歸併排序算法中，我們可以可以看到在進行每一步遞歸的時候，給定的數組會被等分為兩份。
因此，為了分析歸併排序的複雜度，我們需要弄清楚兩件重要的事。
1.我們需要知道樹結構中的每個層級(level)需完成的工作量。
2. 我們需要知道樹的總層數，也就是大家通常所說的樹的高度。
首先，我們要計算一下遞歸樹的高度。從上圖所示的遞歸樹中，我們能看到每個非葉節點都分位兩個節點。因此，這就是一個完整的二叉樹。
我們會一直拆分數值直到子數組中只剩下一個元素(也就是最底層)，這時我們就可以不用排序直接返回了。
在我們的二元遞歸樹的第一層，有一個有N個元素組成的問題。其下一層由兩個子問題(需要進行排序的數組)構成，每個子問題都有N/2個元素。
我們真正關心的並不是有多少子問題，我們只想知道每個子問題的大小，因為在樹結構裡，同一層內的子問題都有一樣的大小。
節點內元素的數量按照2的次方遞減。所以按上述的模式可以表示為：
N = 2^X
X = log_2(N)
這表示樹的高度為log_2(N)(N以2為底求對數)。那就讓我們看一下算法在每一步需要完成的工作量。
我們定義T(N)為對含有N個元素的數組進行排序所需的工作量。
T(N) = 2T(N / 2) + O(N)
這算式表示樹結構中的第一層的工作量為O(N)， 其餘的工作量2T(N / 2)在下一層完成。在下一級，如上圖所示，需完成的工作量是2 * O(N / 2) = O(N)。類似地，在第三層要完成的工作量就是4 * O(N / 4) = O(N)。
令人驚訝的是，該算法在每層上的工作量是相同的，且都等於O(N)，這是歸併操作所消耗的時間。因此，可以用層數來定義總體的時間複雜度數。
如我們前面計算的那樣，遞歸樹的層數是log(N)，因此，歸併排序的時間複雜度就是O(Nlog(N))。
很好，我們掌握了一種用遞歸樹形式進行漸進分析的方法。這是種有趣的方法，可以讓我們很直觀地認識遞歸關係的複雜度。雖然去繪製完整的遞歸樹是不可行的，但遞歸樹有助於我們建立對遞歸關係的理解。
主定理方法
我們研究了基於遞歸樹的分析方法，以實現對遞歸進行漸進分析。但是，如前文所述，每次為了計算複雜度去繪製遞歸樹是不可行的。
歸併排序遞歸只是將問題(數組)劃分為兩個子問題(子數組)。但是，當有算法要把問題分成100份子問題時，我們要怎麼分析呢，顯然不能通過繪製遞歸樹的方式。
因此，我們要用一種更直接的方式來分析遞歸關係的複雜度。通過這種方式，我們不需要實際地繪製遞歸樹，而且這種方式也是基於和遞歸樹一樣的概念上。
主定理方法這時就強勢登場了，它也是基於遞歸樹方法。該方法能應用於三種不同的場景，基本上也就是涵蓋了大部分的遞歸關係。在展示案例之前，我們先看看通用遞歸關係的遞歸樹：
T(n) = a T(n / b) + f(n)
n 是總問題的大小。
a 是遞歸關係中子問題的數量。
n/b 每子問題的的大小(假設子問題大小相同)
f(n) 表示調用遞歸之外的工作成本，包括將問題劃分為較小子問題的成本及合併子問題解決方案的成本。
想理解主定理方法，有兩點最重要，分別是算法在根節點的工作量和在葉節點工作量。
根節點工作量相對點簡單，就是f(n)。葉節點的工作量取決於其所在樹上的高度。
樹的高度為log_b(n)，也就是以b為底取n的對數。這和歸併排序的遞歸樹道理一樣，而在歸併排序中b就是2。在任意層l的節點數量就是a^l，所以最後一層的葉節點數可由如下算式所得：
a^{log_b(n)} = n ^ log_b(a) nodes.
假設在末層完成每個子問題所需的工作量為Θ(1)，因此在葉節點處完成的工作量就是n ^ log_b(a)。
如果你認真觀察通用遞歸關係，你會發現如下兩個成分：
1.分部步驟(/)算子，這部分會不斷複製並不斷乘以值越來越小的本身。
2.治理步驟() 算子，這部分會把迷你部分聚集在一起。
這兩股力量似乎在相互對抗，這樣一來，他們想控制算法的總工作量，從而控制整體時間複雜度。
誰會佔主導呢？我們需要分三種情況討論
情況1(分部步驟獲勝)
如果f(n) = Θ(n^c)，使得c < log_b(a)，那麼可得出T(n) = Θ(n^log_b(a))。其中f(n)是根節點處工作量，n ^ log_b(a)是葉節點的工作量。
如果葉節點的工作量是多項式形式的，那計算結果就是葉節點的工作量。
e.g. T(n) = 8 T(n / 2) + 1000 n^2
在這個例子中，a = 8，b = 2，f（n）= O（n ^ 2）
因此， c = 2且log_b（a）= log_2（8）= 3
顯然2 <3， 並且很容易看出這適用於Master方法的案例1。這意味著，在樹葉處完成的工作量漸近地高於在根處完成的工作量。因此，該遞歸關係的複雜度是 Θ（n ^ log_2（8））=Θ（n ^ 3）。
案例2（治理步驟獲勝）
如果 f（n）=Θ（n ^ c） 使得 c> log_b（a） ，則 T（n）=Θ（f（n）） 。如果在根節點上完成的工作漸進式更多，那麼我們的最終複雜度就是根節點的複雜度。
我們並不關心較低級別的工作量，因為最大的多項式項依賴於控制算法複雜度的n。因此，所有較低級別上的工作可以被忽略。
例如T（n）= 2T（n / 2）+ n ^ 2
如果在主定理方法中適合這種遞歸關係，我們可以得到：
a = 2, b = 2, and f(n) = O(n^2)
因此， c = 2且log_b（a）= log_2（2）= 1
顯然2> 1，因此這符合Master方法的情況2，其中大部分工作是在遞歸樹的根處完成的，這就是為什麼 Θ（f（n））控制算法的複雜度的原因。因此，該遞歸關係的時間複雜度是Θ（n ^ 2）。
案例3 （平局！）
如果 f（n）=Θ（n ^ c） 使得 c = log_b（a） ，則 T（n）=Θ（n ^ c * log（n））。最後一種情況是，在葉上完成的工作和在根處完成的工作之間打成平局。
在這種情況下，治理和分步驟同樣佔主導地位，因此完成的工作總量等於在任何級別完成的工作量*樹的高度。
例如T（n）= 2T（n / 2）+ O（n）
等等，這不就是歸併排序嘛！
對!這就是歸併排序算法的複雜度。如果我們在主定理方法中採用歸併排序的遞歸關係，我們得到：
a = 2，b = 2，f（n）= O（n ^ 2）
因此， c = 1 = log_2（2）
這符合上述案例3中的標準。通過上面的數字可以證明所有級別的工作量都將相等。因此，時間複雜度等於在任何級別的工作量*所有級別數（或者是樹的高度）。
我們使用兩種不同的方法分析了歸併排序算法的時間複雜度，即遞歸樹和主定理法。因為歸併排序算法是一種遞歸算法，我們之前看到的用於解決循環問題的經典漸近分析方法在這裡沒用到。
空間複雜度：對於空間複雜度，我們不必使用任何複雜的技術，因此分析更簡單。在歸併排序算法中佔用數據結構的一個主要空間是合併過程中使用的臨時緩衝區。這個數組被初始化一次，此數組的大小是 N。佔用空間的另一種數據結構是遞歸堆棧。實質上，遞歸調用的總數決定了遞歸堆棧的大小。正如我們在遞歸樹表示中看到的那樣，歸併排序調用的次數基本上是遞歸樹的高度。
遞歸樹的高度是 log_2（N） ，因此，遞歸堆棧的最大也就是log_2（N） 。
因此，歸併排序的總空間複雜度將是 N + log_2（N）= O（N） 。
二進位搜索
還記得嗎，皮卡丘想要尋找特定能力的神奇寶貝。小皮卡丘有1000 個小夥伴，他必須找到一個具有特定能力的神奇寶貝。是的，皮卡丘對他的對手非常挑剔。
他的要求一天一個變，每當他的要求發生變化時，他肯定不能去檢查每一個神奇寶貝，也就是說他不能通過執行線性搜索來找到他正在尋找的目標。
我們之前提到使用哈希表來存儲神奇寶貝的數據，用它們的能力作為key，神奇寶貝本身作為value。這會降低搜索的複雜度至O（1）即恆定時間。
然而，在考慮到有N個神奇寶貝可用的情況下，這會用到額外的空間使搜索操作的空間複雜度提高到 O（N） 。在這種情況下，N將是1000。如果皮卡丘沒有這些額外的空間，但仍然想加快搜索過程，那要怎麼辦呢？
沒錯！皮卡丘可以利用他對排序算法的深刻了解，想出一種比慢速線性搜索更快的搜索策略。
皮卡丘決定向他的好朋友代歐奇希斯尋求幫助。代歐奇希斯可以幫助皮卡丘根據寶貝的能力值重新排列神奇寶貝列表。
代歐奇希斯使用快速排序算法，而不是傳統的排序算法對神奇寶貝排序。
這麼一來，他沒有使用任何額外的空間，並且排序 N個神奇寶貝所花費的時間與歸併排序算法一樣。
之後，皮卡丘非常聰明地提出了一種搜索策略，利用了神奇寶貝列表的排序特性。
這種新的策略/算法被稱為二進位搜索 算法。（ 註：排序是運行二進位搜索的前提條件，一旦列表被排序後，皮卡丘可以在此排序列表上多次運行二進位搜索）。
讓我們看看這個算法的代碼，然後分析它的複雜性。
顯然，該算法的本質是遞歸。我們嘗試用新學到的技巧來分析二進位搜索算法的時間複雜度。這兩個變量l和r基本上定義了數組中我們必須搜索對給定要素x的部分 。
如果我們看一下算法，它所做的一切就是將輸入數組的搜索部分分成兩半。除了根據某種條件進行遞歸調用之外，它實際上並沒有做任何事情。那麼，讓我們快速查看二進位搜索算法的遞歸關係。
T(n) = T(n / 2) + O(1)
這看起來好像是一個非常簡單的遞歸關係。首先讓我們嘗試分析遞歸樹並從中得出複雜性，然後我們將使用主定理方法，看看三種情況中哪一種適合這種遞歸。
哇！這種二進位搜索算法非常快。它比線性搜索快得多。這對我們可愛的好朋友皮卡丘來說意味著，在1000隻小精靈中，他最多只需要去詢問其中的10個，就可以找到他特殊的口袋妖怪。
現在讓我們看看如何採用更「公式化」的方法進行遞歸複雜度分析。Master方法在這種情況下對我們有所幫助。通用主方法的遞歸關係是
T(n) = a T(n / b) + f(n)
而對於我們的二進位搜索算法，我們有
T(n) = T(n / 2) + O(1)
f(n) = O(n^0), hence c = 0
a = 1
b = 2
c = 0
對於Master定理來說有3種不同的情況，而c和 log_b（a）是其中的影響因素。在我們的例子中，0 =log_2（1）即0 = 0的時候，二分搜索算法符合主定理的情況3，因此T(n) = Θ(n^0 log(n)) = Θ(log(n)
如何選擇最好的算法？
在本文中，我們介紹了複雜性分析的概念，它是算法設計和開發的重要部分。我們看到為什麼分析算法的複雜性很重要，以及它如何直接影響我們的最終決策。我們甚至看到了一些有效和正確分析這種複雜性的優秀技術，以便及時做出明智的決策。然而，問題出現了，
鑑於我所知道的兩種算法的時間和空間複雜性，我該如何選擇最終使用哪種算法？有黃金法則嗎？
很遺憾，答案是，沒有。
沒有黃金法則可以幫助你決定使用哪種算法。這完全取決於很多外部因素。看看以下幾種情況的例子吧！
空間無約束
如果你有兩個算法A和B，並且你想要決定使用哪個算法，除了時間複雜度之外，空間複雜度也會成為一個重要因素。
但是，考慮到空間不是你所關心的問題，最好採用能夠在更多空間的情況下進一步降低時間複雜度的算法。
例如，Counting Sort是一種線性時間排序算法，但它在很大程度上取決於可用空間量。確切地說，它可以處理的數字範圍取決於可用空間的大小。給定無限空間，你最好使用Counting Sort算法對大量數字進行排序。
亞秒級延遲要求和可用空間有限
如果你發現自己處於這種情況，那麼深入了解算法在許多不同輸入上的性能變得非常重要，尤其是你期望算法在你的應用程式中使用的輸入類型。
例如，我們有兩種排序算法：冒泡排序和插入排序，你要在其中決定使用哪一種用於根據用戶年齡對用戶列表進行排序。你分析了預期的輸入類型，並且你發現輸入數組幾乎已經排序。在這種情況下，最好採用插入排序。
等等，為什麼有人會在現實中用插入排序或者冒泡排序？
的確，很多人認為這些算法僅用於教育目的而未在任何真實場景中使用。但實際並非如此。
比如Python中的sort（）功能。它就使用了基於插入排序和歸併排序的混合算法，稱為Tim Sort算法。
確實，插入排序可能對非常大的輸入沒有用，正如我們從其多項式時間複雜度中看到的那樣。然而，它卻能迅速處理幾乎排好序的數組，這正是它在Timsort算法中使用的原因。
簡而言之，不同算法之間不會有明確的黑白劃分。
算法的屬性，如它們的時間和空間複雜性，都是非常重要的考慮因素。算法使用的輸入大小以及可能存在的任何其他約束也有可能產生影響。
考慮到所有這些因素，我們才能做出明智的決定！
本文首發於微信公眾號：大數據文摘。文章內容屬作者個人觀點，不代表和訊網立場。投資者據此操作，風險請自擔。
（責任編輯：季麗亞 HN003）