如果說計算機科學中第一重要的思想是遞歸，第二重要的恐怕就是分治算法（Divide and Conquer）。對分治算法理解的程度，是衡量一個人計算機科學素養的標尺。本章從三個層次由淺入深地介紹分治算法的原理和應用。

分治算法的道理很簡單，基本上就是三步：

• 分割（Divide）：將一個複雜的問題分成若干個簡單的子問題
• 征服（Conquer）：解決每一個子問題
• 合併（Combine）：對子問題的結果進行合併，得到原有問題的解

6.1 分治：從 O(N²) 到 O(NlogN)#

歸併排序（Merge Sort）#

• 大部分學習計算機科學的人接觸分治算法都是從歸併排序開始的
• 核心思路：將大數組一分為二，分別排序後再合併
• 合併兩個已排好序的序列，只需要 O(m+n) 的計算量
• 歸併排序的遞歸公式：F(N) = 2F(N/2) + kN
• 展開後得到 F(N) = O(NlogN)，將排序的複雜度從 O(N²) 降到了 O(NlogN)

空間複雜度#

• 歸併排序實際上只需要 O(N) 的額外空間
• 在遞歸過程中，上一層的目標數據空間就是下一層的源數據空間，兩份數據空間交替使用

25 名選手爭奪前三名的問題#

• 運用歸併排序中的合併步驟，巧妙地在 7 次比賽中選出前三名
• 關鍵在於利用已有的比賽信息，避免無用的比較
• 這個問題考查的是能否靈活運用分治算法的思想，而非生搬硬套

從 N 個排好序的序列中選出 K 個最大元素#

• 利用堆（Heap）數據結構，可以實現 N 選 K 的操作
• 建立一個 K+1 元素的最小堆，不斷用序列中的元素和堆頂比較
• 時間複雜度為 O((K+N)logN)，當 K 遠小於 N 時效果最佳

要點：利用堆這樣一個數據結構，可以實現 N 選 K 的操作。當 K 遠小於 N 時，這種方法幾乎是最佳的。

6.2 分割算法：快速排序和中值問題#

快速排序（Quick Sort）#

• 與歸併排序類似，都是先分割再排序，但有兩個不同：
  • 分割時不是從中間直接分開，而是按照極值（Pivot Value）將大的放一邊、小的放另一邊
  • 合併步驟不需要做任何比較，因為分割時已保證左邊都比極值小、右邊都比極值大
• 平均複雜度為 O(NlogN)，最壞情況（數組已排好序）為 O(N²)
• 平均速度是歸併排序的三倍，自 1960 年霍爾發明後一直是全世界使用最多的排序算法

分割算法求中值#

• 中值問題：從未排序的大數組中找到中間大小的元素
• 使用分割算法可以達到 O(N) 的線性複雜度，遠優於排序後取中值的 O(NlogN)
• 核心思想：每次分割後，只需要在包含目標位置的那一半繼續查找
• 計算量為 N + Nr + Nr² + … = N/(1-r)，約為 3N

分布式中值算法#

• 當數據量大到一台服務器存不下時，需要分布式解決
• 關鍵思路：用一個極值來對整個序列分割，而非讓每台服務器獨自運行
• 各台服務器在本地進行分割，然後匯報結果給協調服務器，由協調服務器決定下一次的極值
• 分治算法的精髓是將不容易解決的大問題分解為小問題，而不是簡單的二分遞歸

要點：利用分割算法可以在 O(N) 時間內找到一個大數組的中值。這種方法之所以比排序算法快，是因為它不需要比較任意兩個元素的大小。

6.3 並行初探：矩陣相乘和 MapReduce#

大規模矩陣乘法#

• Google 的 PageRank 計算本質上是矩陣相乘問題
• 當矩陣規模達到幾億乘幾億時，無法在一台服務器上完成計算
• 解決方案：將矩陣按行和列分割，分配到多台服務器上

不同資源條件下的方案#

• 10 台服務器：將矩陣 A 按行分為 10 份，矩陣 B 在服務器間循環傳遞
• 100 台服務器：將 A 和 B 各分為 10 份，每台服務器計算一個子矩陣的乘積
• 1000 台服務器：進一步將每台服務器的計算拆分為 10 份分配給 10 台服務器，再由特定服務器合併中間結果——這就是 MapReduce 的根本原理

MapReduce#

• 將一個大任務拆分成小的子任務計算（Map，分割），再將中間結果合併成最終結果（Reduce，合併）
• MapReduce 的設計者對分治算法的理解遠遠超出一般從業者，他們不僅知道如何將大量複雜的計算通過分治算法來解決，還能開發出比較通用的工具來解決一大批問題
• 兩位主要發明者傑夫·迪安和桑傑·戈馬瓦特因此當選美國工程院院士

要點：根據不同數量的資源，設計不同的方法解決同樣的問題。理想的情況是，增加 10 倍的資源，計算速度也能增加 10 倍。

6.4 從機器學習到深度學習：Google 大腦#

機器學習與分治#

• 機器學習的訓練算法計算量大而且不好拆分
• 通常做法是按照數據切分，分配到多台服務器上並行訓練
• 但模型特徵之間可能有關聯性，因此有時需要將相關特徵放在同一台服務器上

深度學習與人工神經網絡#

• 深度學習本質上是一個層次很深的人工神經網絡
• 網絡的輸入層、中間層（隱藏層）和輸出層之間通過有權重的邊傳遞數值
• 訓練的目標是調整邊的權重，使成本函數降到最低

Google 大腦#

• Google 大腦是一個通用的深度學習工具，採用深度人工神經網絡
• 訓練的難點在於不僅要把數據分割成小子集，還需要把人工神經網絡切成數千塊
• 每一塊的訓練不是完全獨立的，需要考慮上下左右很多塊的計算結果
• Google 在工程上做了合理的近似，解決了特徵解耦合的難題
• 三位提出深度學習基礎算法的學者——杰弗里·辛頓、約書亞·本吉奧和楊立昆——因此獲得了圖靈獎

分治算法的三個理解層次#

• 第一層次：理解大致原理，能套用教科書中的例子解決問題
• 第二層次：理解分治的本質，能用這個工具解決前人沒有遇到的新問題——在工業界可以立足
• 第三層次：對分治算法的應用有所貢獻，能在學術界立足——需要豐富的經驗和扎實的理論基礎

要點：分治算法的第三個層次就是吃透了這種方法的精髓，能夠分解看似耦合度很高的任務，在算法上有所突破。