定義
將原問(wèn)題劃分成n個(gè)規(guī)模較小，并且結(jié)構(gòu)與原問(wèn)題相似的子問(wèn)題，遞歸地解決這些子問(wèn)題，然后再合并其結(jié)果，就得到原問(wèn)題的解。
每一次遞歸都會(huì)涉及三個(gè)操作
- 分解：將原問(wèn)題分解成一系列子問(wèn)題；
- 解決：遞歸地求解各個(gè)子問(wèn)題，若子問(wèn)題足夠小，則直接求解；
- 合并：將子問(wèn)題的結(jié)果合并成原問(wèn)題；
使用分治算法的前提條件
- 原問(wèn)題與分解成的小問(wèn)題具有相同的模式；
- 原問(wèn)題分解成的子問(wèn)題可以獨(dú)立求解，子問(wèn)題之間沒(méi)有相關(guān)性，這一點(diǎn)是分治算法跟動(dòng)態(tài)規(guī)劃的明顯區(qū)別；
- 具有分解終止條件，也就是說(shuō)，當(dāng)問(wèn)題足夠小時(shí)，可以直接求解；
- 可以將子問(wèn)題合并成原問(wèn)題，而這個(gè)合并操作的復(fù)雜度不能太高，否則就起不到減小算法總體復(fù)雜度的效果了。
分治算法實(shí)踐
- 如何編程求出一組數(shù)據(jù)的有序?qū)€(gè)數(shù)或者逆序?qū)€(gè)數(shù)呢？
解答：使用歸并排序算法
public class MergeSort {
private int num = 0;
public int count(int[] a, int n) {
num = 0;
mergeSortCount(a, 0, n - 1);
return num;
}
private void mergeSortCount(int[] a, int p, int r) {
if (p >= r) {
return;
}
int q = (p + r) / 2;
mergeSortCount(a, p, q);
mergeSortCount(a, q + 1, r);
merge(a, p, q, r);
}
private void merge(int[] a, int low, int middle, int high) {
int i = low;
int j = middle + 1;
int k = 0;
int[] tmp = new int[high - low + 1];
while (i <= middle && j <= high) {
if (a[i] <= a[j]) {
tmp[k++] = a[i++];
}
else {
num += (middle - i + 1); //統(tǒng)計(jì)middle-low之間，比a[j]大的元素個(gè)數(shù)
tmp[k++] = a[j++];
}
}
while (i <= low) {
tmp[k++] = a[i++];
}
while (j <= high) {
tmp[k++] = a[j++];
}
for (i = 0; i <= high - low; ++i) {
a[low + i] = tmp[i];
}
}
}
二位平面上有n個(gè)點(diǎn)，如何快速計(jì)算出兩個(gè)距離最近的點(diǎn)對(duì)？
解答：分成兩塊單獨(dú)求其中一塊點(diǎn)對(duì)最小距離，然后求這兩塊之間點(diǎn)對(duì)的最小距離，通過(guò)一些排序和刪除，可以減少到6個(gè)點(diǎn)之間比較。有兩個(gè)nn的矩陣A，B，如何快速求解兩個(gè)矩陣的乘積C=AB?
解答：v.斯特拉森提出了2*2分塊矩陣的計(jì)算公式 從原來(lái)的8次乘法 縮減到了7次
當(dāng)n規(guī)模很大的時(shí)候 縮減效果就很明顯 （7/8）^(logn)給10GB的訂單文件按照金額排序？
解答：我們先掃描一遍訂單，根據(jù)訂單的金額，將10GB的文件劃分為幾個(gè)金額區(qū)間。為什么說(shuō)MapReduce的本質(zhì)就是分治思想？
解答：MapReduce框架只是一個(gè)任務(wù)調(diào)度器，底層依賴(lài)GFS來(lái)存儲(chǔ)數(shù)據(jù)，依賴(lài)Borg管理處理器。它從GFS中拿數(shù)據(jù)，交給Borg中的機(jī)器執(zhí)行，并且時(shí)刻監(jiān)控機(jī)器執(zhí)行的速度，一旦出現(xiàn)機(jī)器宕機(jī)、進(jìn)度卡殼等，就重新從Borg中調(diào)度一臺(tái)機(jī)器執(zhí)行。
典型的應(yīng)用場(chǎng)景
- 用來(lái)指導(dǎo)編碼，降低問(wèn)題求解的時(shí)間復(fù)雜度
- 解決海量數(shù)據(jù)處理問(wèn)題
解釋
Google文件系統(tǒng)（英語(yǔ)：Google File System，縮寫(xiě)為GFS或GoogleFS），一種專(zhuān)有分布式文件系統(tǒng)，由Google公司開(kāi)發(fā)，運(yùn)行于Linux平臺(tái)上
BigTable是一種壓縮的、高性能的、高可擴(kuò)展性的，基于Google文件系統(tǒng)（Google File System，GFS）的數(shù)據(jù)存儲(chǔ)系統(tǒng)，用于存儲(chǔ)大規(guī)模結(jié)構(gòu)化數(shù)據(jù)，適用于云端計(jì)算
MapReduce是Google提出的一個(gè)軟件架構(gòu),用于大規(guī)模數(shù)據(jù)集（大于1TB的并行運(yùn)算)。
創(chuàng)新并非離我們很遠(yuǎn)，創(chuàng)新的源泉來(lái)自對(duì)事物本質(zhì)的認(rèn)識(shí)。無(wú)數(shù)優(yōu)秀架構(gòu)設(shè)計(jì)的思想來(lái)源都是基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)和算法，這本身就是算法的一個(gè)魅力所在。
