貪心算法
回溯算法
分治算法
動態規劃

MapReduce本質就是分治算法，是Google大數據處理的三駕馬車之一，另外兩個是GFS和Bigtable。它在倒排索引，PageRank計算，網頁分析等搜索引擎相關的技術中都有大量的應用。
MapReduce 框架只是一個任務調度器，底層依賴 GFS 來存儲數據，依賴 Borg 管理機器。它從 GFS 中拿數據，交給 Borg 中的機器執行，并且時刻監控機器執行的進度，一旦出現機器宕機、進度卡殼等，就重新從 Borg 中調度一臺機器執行。

一：如何理解分治算法

1，分治算法的核心思想其實就是四個字，分而治之，將原問題劃分成n個規模較小，并且結構與原問題相似的子問題，遞歸地解決這些子問題，然后在合并其結果，就得到原問題的解。

2，分治算法的定義類似于遞歸，但區別在于：分治算法是一種處理問題的思想，遞歸是一種編程技巧。

3，分治算法一般都比較適合遞歸來實現，分治算法的遞歸實現中，每一層遞歸都會涉及這樣的三個操作：
分解：將原問題分解成一系列子問題；
解決：遞歸地求解各個子問題，若子問題足夠小，則直接求解；
合并：將子問題的結果合并成原問題；

4，分治算法能解決的問題，一般需要滿足下面這幾個條件：
原問題與分解成的小問題具有相同的模式；
原問題分解成的子問題可以獨立求解，子問題之間沒有相關性，這一點是分治算法跟動態規劃的明顯區別，
? 具有分解終止條件，即當問題足夠小時，可以直接求解。
? 可以將子問題合并成原問題，而這個操作的復雜度不能太高，否則就起不到減小算法總體復雜度的效果。

二：分治算法應用舉例分析

假設有n個數據，期望數據從小到大排序，那完全有序的數據的有序度就是n(n-1)/2。逆序度等于0；相反，倒序排序的數據的有序度就是0，逆序度是n(n-1)/2。除了這兩中極端情況外，我們通過計算有序對或逆序對的個數，來表示數據的有序度或逆序度。

現在問：如何編程求出數組中的數據有序對個數或逆序對個數？
1，最簡單的辦法：拿每個數字和他后面的數字比較，看有幾個比它小。將比它小的數字個數記作k，通過這樣的方式，把每個數字都考察一遍后，對每個數字對應的k值求和，最后得到的總和就是逆序對個數。但時間復雜度是O(n^2)。
2，用分治算法，套用分治的思想，將書中分成前后兩半A1和A2，分別兩者中的逆序對數，然后在計算A1和A2之間的逆序對個數k3。那整個數組的逆序對個數就是k1+k2+k3。
要快速計算出兩個子問題A1和A2之間的逆序對個數需要借助歸并排序算法。
歸并排序算法有個非常關鍵的操作，即將兩個有序的小數組，合并成一個有序的數組。實際上，在合并的過程中，就可以計算這兩個小數組的逆序對個數。每次合并操作，都計算逆序對個數，把這些計算出來的逆序對個數求和，就是這個數組的逆序對個數。

private int num = 0; // 全局變量或者成員變量public int count(int[] a, int n) {num = 0;mergeSortCounting(a, 0, n-1);return num; }private void mergeSortCounting(int[] a, int p, int r) {if (p >= r) return;int q = (p+r)/2;mergeSortCounting(a, p, q);mergeSortCounting(a, q+1, r);merge(a, p, q, r); }private void merge(int[] a, int p, int q, int r) {int i = p, j = q+1, k = 0;int[] tmp = new int[r-p+1];while (i<=q && j<=r) {if (a[i] <= a[j]) {tmp[k++] = a[i++];} else {num += (q-i+1); // 統計p-q之間，比a[j]大的元素個數 !!!! 統計tmp[k++] = a[j++];}}while (i <= q) { // 處理剩下的tmp[k++] = a[i++];}while (j <= r) { // 處理剩下的tmp[k++] = a[j++];}for (i = 0; i <= r-p; ++i) { // 從tmp拷貝回aa[p+i] = tmp[i];} }

三：分治思想在海量數據處理中的應用

假設，給10GB的訂單文件按照金額排序這樣一個需求，看似是一個簡單的排序問題，但是因為數據量大，有10GB，而我們的機器的內存可能只有2,3GB這樣子，無法一次性加載到內存，也就無法通過單純地使用快排，歸并等基礎算法來解決。

要解決這種數據量大到內裝不下的問題，我們就可以利用分治的思想，將海量的數據集合根據某種方法，劃分為幾個小的數據集合，每個小的數據集合單獨加載到內存來解決，然后在將小數據集合合并成大數據集合，實際上利用這種分治的處理思路，不僅能克服內存的限制，還能利用多線程或者多機處理，加快處理的速度。

采用分治思想的算法：快排、合并排序、桶排、基數排序、二分查找、遞歸樹、數據庫分片、MapReduce

創新的源泉來自對事物本質的認識，無數優秀架構設計的思想來源都是基礎的數據結構和算法。

筆記整理來源： 王爭 數據結構與算法之美

總結

以上是生活随笔為你收集整理的【数据结构与算法】【算法思想】分治算法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。