分治技術(shù)課件

分治技術(shù)

3.1分治策略的思想

3.2大整數(shù)乘法

3.3矩陣相乘的Strassen算法

3.4選擇（Selection）問題的線性算法

13.1分治策略的思想分治算法把一個(gè)規(guī)模為n的問題實(shí)例劃分為若干個(gè)規(guī)模較小的子問題：其規(guī)模分別為然后遞歸地解這k個(gè)子問題，最后把k個(gè)子結(jié)果合并為整個(gè)問題的解。分治算法的幾個(gè)要點(diǎn)是：遞歸基礎(chǔ)：為了保證遞歸過程在有限步驟內(nèi)結(jié)束，當(dāng)n值小于某常數(shù)n0

時(shí)，要有一個(gè)簡(jiǎn)單的處理算法。2劃分：分治把長(zhǎng)為n的問題實(shí)例分成幾個(gè)部分。許多分治算法簡(jiǎn)單地取k=2。為了算法有好的性能，劃分應(yīng)該盡量平衡。遞歸：就是用同樣的方法去解各個(gè)子問題。如果k個(gè)子問題的長(zhǎng)度為n1，n2，…，nk

，那么算法執(zhí)行的總代價(jià)和各個(gè)子問題的代價(jià)應(yīng)分別為T(n)和T(n1)，T(n2)，..，T(nk)。合并結(jié)果：幾個(gè)子問題獲得解決之后，各個(gè)結(jié)果應(yīng)合并為整個(gè)問題的解。解的合并的代價(jià)因情況不同而異。33.2大整數(shù)乘法3.2.1選擇排序（SelectionSorting）

設(shè)Х和Ｙ是兩個(gè)n位的二進(jìn)制數(shù)，按傳統(tǒng)方法計(jì)算乘積Х·Ｙ，需要O(n2)次位運(yùn)算。為簡(jiǎn)化問題，設(shè)n=2k，k為正整數(shù)。當(dāng)n=1時(shí)，計(jì)算Х·Ｙ就是一次位乘。對(duì)Х、Ｙ進(jìn)行劃分：X=A·2n/2+BY=C·2n/2+DA,B,C,D為n/2位的二進(jìn)制數(shù)。ABCDX:Y:4則有：Х·Ｙ=AC·2n+(AD+BC)·2n/2+BD

按上式可以把計(jì)算Х·Ｙ的問題劃分為四個(gè)子問題。即計(jì)算n/2位的二進(jìn)制數(shù)的乘積AC，AD，BC，BD。用同樣方式計(jì)算完成之后，再通過三次n/2位的加法和兩次移位，合并為Х·Ｙ。顯然，合并代價(jià)為O(n)階。因此得到遞歸方程如下：

根據(jù)主項(xiàng)定理得：（公式3.2）

（公式3.1）

5與我們所期望的不同，簡(jiǎn)單的分治策略未達(dá)到改進(jìn)的目的。事實(shí)上，把一個(gè)n位數(shù)乘法化為4次n/2位數(shù)乘法是不可能改進(jìn)O(n2)的復(fù)雜度的。幸運(yùn)的是，Х·Ｙ可以有另一計(jì)算公式：X·Y=AC·2n+[(A-B)(D-C)+BD+AC]·2n/2+BD公式3.3只有AC、BD和(A-B)(D-C)三次n/2位數(shù)的乘法，其合并代價(jià)稍有增加，6次加減法、2次移位，仍為O(n)階。時(shí)間復(fù)雜度的遞歸方程為：

（公式3.4）（公式3.3）

6方程的解為：這個(gè)算法的設(shè)計(jì)過程指明：1.

分治策略用于算法設(shè)計(jì)，往往需要一些技巧。2.

表面上分治只是把一個(gè)大問題分成幾個(gè)子問題，分別計(jì)算然后再合并為問題的解，似乎沒有明顯的節(jié)省，但效果卻很顯著。對(duì)于最大元最小元問題，分治策略把計(jì)算代價(jià)從2n–3減為3n/2–2，大致減少了1/4的工作量；而在n位數(shù)乘問題中，代價(jià)從O(n2)減少到O(n1.59)，當(dāng)n較大時(shí)，可能會(huì)成倍的減速，因?yàn)榫蚽0.41這個(gè)因子來說，在n=1000時(shí)，它大于16。73.3矩陣相乘的Strassen算法

3.3.1問題矩陣運(yùn)算中，矩陣的元素一般為整型和實(shí)型，其基本操作是實(shí)數(shù)或整數(shù)乘法，當(dāng)數(shù)的有效數(shù)字位數(shù)較多時(shí)，數(shù)的加法較數(shù)的乘法占用時(shí)間較少。已知：n階矩陣A,B，計(jì)算乘積C=A·B，計(jì)算公式為：其中cij，aij，bij為矩陣C，A，B的元素。顯然，完成計(jì)算共需n3次乘法和n2(n-1)次加法。（公式3.5）83.3.2分治為了簡(jiǎn)化問題，設(shè)n=2k，k為正整數(shù)。直接把矩陣A，B，C一分為四，化為n/2階矩陣：矩陣乘積C=A·B分解為：（公式3.6）93.6式共需8次n/2階矩陣相乘和4次n/2階矩陣相加。顯然后者為θ(n2)次數(shù)的加法，一般乘法代價(jià)高于加法，故也可記為O(n2)次乘法。分治算法的時(shí)間代價(jià)可由下面的遞歸方程表示：根據(jù)主項(xiàng)定理可知：

遺憾是，簡(jiǎn)單的分治未能使算法得到改進(jìn)。（公式3.7）

103.3.3Strassen的分治方法V.Strassen發(fā)現(xiàn)公式3.6中的8次矩陣乘法是相關(guān)的，他給出了只需7次n/2階矩陣乘法的算法，付出的代價(jià)是原來的4次n/2階矩陣相加，增加到18次加（減）法運(yùn)算。從求解3.7式的過程可知，時(shí)間代價(jià)函數(shù)滿足：其解為：終于獲得了改進(jìn)。113.3.4Strassen算法的描述算法可以分為下面三步：1.

把n階矩陣A，B劃分為8個(gè)n/2階子矩陣： A11，A12，A21，A22，B11，B12，B21，B22。2.

通過7次n/2階矩陣相乘，得到n/2階矩陣M1，M2，..，M7：M1=A11(B12–B22)M2=(A11+A12)B22M3=(A21+A22)B11

M4=A22(B21–B11)M5=(A11+A22)(B11+B22)M6=(A12-A22)(B21+B22)M7=(A11-A21)(B11+B12)12132.

Strassen把8次子矩陣相乘成功地減少為7次。已經(jīng)證明，采用3.6式的劃分方法，至少需要7次乘法，不能再改進(jìn)了。當(dāng)然，不同的劃分方法，例如把矩陣A，B劃分為3×3，5×5個(gè)子矩陣，也是可以的。3.

由于矩陣乘法是一個(gè)重要的計(jì)算問題，許多人努力設(shè)計(jì)更好的算法。在Strassen之后，O(n2.81)這個(gè)時(shí)間階曾多次被改進(jìn)，分別為：O(n2.795)，O(n2.78)，O(n2.548)，O(n2.494)，目前已知的最好算法達(dá)到O(n2.376)。4.算法至今只知道一個(gè)平凡的下界Ω(n2)。5.

Strassen算法雖然把時(shí)間代價(jià)從θ(n3)降至θ(n2.81)階，但后者的系數(shù)要比1大很多。當(dāng)n比較?。ɡ鏽<45）且當(dāng)矩陣中非零元素較少時(shí)，不宜采用此種方法。對(duì)于稀疏矩陣的運(yùn)算，還有其它特殊的有效算法。

143.4選擇問題的線性算法3.4.1問題選擇問題簡(jiǎn)單地說就是求n元中的第k元，它與排序問題、比賽問題可以歸屬于同一類，只是具體要求有區(qū)別。它們都是以n個(gè)某全序集上的元素作為輸入，排序問題是求n個(gè)元的全部順序；比賽問題是只求前k個(gè)元的正確順序；而選擇問題是求第k元，對(duì)前k–1個(gè)元的順序不關(guān)心，對(duì)后n–k個(gè)元的順序也不關(guān)心，當(dāng)k=1時(shí)即是最小元問題。選擇問題的另一個(gè)特例是中值問題。3.4.2簡(jiǎn)單算法解選擇問題最簡(jiǎn)單的解法是直接使用排序算法，對(duì)n元L[1..n]進(jìn)行排序后，取L[k]即為所求。不過最好的排序算法的復(fù)雜度為O(nlogn)階。15從選擇問題容易想到快速排序算法中的劃分，實(shí)際上它是求劃分元位于位置k的劃分。算法3.1簡(jiǎn)單的選擇算法當(dāng)取k滿足1≤k≤n時(shí)，對(duì)L[1..n]調(diào)用函數(shù)QSelect(L,1,n,k)，即可得到所求。這個(gè)算法與QuickSort算法十分相近，其區(qū)別在于在劃分后，只選k所在的一側(cè)進(jìn)行遞歸。因此肯定比QuickSort花費(fèi)的時(shí)間代價(jià)要小。事實(shí)上，平均情形下算法QSelect的時(shí)間復(fù)雜度為O(n)階，但在最壞情形下卻與快速排序一樣是O(n2)階。3.4.3O(n)階選擇算法的思路1.

雖然采用了分治策略，但上面的算法在最壞情形下的時(shí)間復(fù)雜度仍然是O(n2)階的。因?yàn)閯澐炙惴≒artition無法避免劃分元位于數(shù)組的兩端的情況。因此問題的關(guān)鍵是，能否花費(fèi)O(n)代價(jià)改進(jìn)劃分算法，保證每次劃分的分點(diǎn)不接近兩端。162.

一個(gè)較復(fù)雜的劃分方案：為了實(shí)現(xiàn)上述目標(biāo)，把n元分為個(gè)5元組，最后一組可能不足5元，可以用最大數(shù)補(bǔ)足。在每個(gè)5元組中求中值，得到一個(gè)由

中值組成的集合M，然后遞歸地求出這些中值的中值m*，以這個(gè)m*作為劃分元。3.

分治：以m*為劃分元，把原數(shù)組L[1..n]的n個(gè)元組成的集合S分為三部分：S1，m*，S2。集合S1中的元素不大于m*，S2中的元素不小于m*。根據(jù)k值的大小，決定如何遞歸。3.4.4算法Select輸入：由L[1..n]全部元素組成的集合S和整數(shù)k，滿足1≤k≤n。設(shè)L[1..n]的元素各不相同。輸出：S中的第k個(gè)最小元。算法3.2Select1718算法Select主要調(diào)用三個(gè)子函數(shù)，第一個(gè)是對(duì)n≤5時(shí)，求第k（≤5）元的算法，因?yàn)橹徽{(diào)用一次，不必精心設(shè)計(jì)。5元排序選擇算法至多用10次比較就能完成。第二個(gè)調(diào)用的是Select3in5()，這個(gè)函數(shù)是在五元中求第三元，在一次遞歸中需要調(diào)用次，因此應(yīng)設(shè)計(jì)一個(gè)較好的算法。第三個(gè)子函數(shù)是劃分算法MPartition()，顯然它的執(zhí)行依賴于劃分元m*的計(jì)算過程。實(shí)際上在m*的計(jì)算過程中，已經(jīng)確定了肯定小于m*的A組元素和大于m*的D組元素，算法MPartition()只需把B、C組元素與m*比較就可以了。算法的設(shè)計(jì)并沒有對(duì)占用空間和元素移動(dòng)作特殊的要求，因此它可以有多種不同的處理方法。193.4.5算法Select的分析設(shè)數(shù)組長(zhǎng)度n為5的奇數(shù)倍，n=5(2r+1)，r為一非負(fù)整數(shù)，忽略在第2、4步遞歸調(diào)用時(shí)數(shù)組長(zhǎng)度不滿足這個(gè)假設(shè)引起的誤差。下面是算法在最壞情形求n元中第k個(gè)最小元所需的比較次數(shù)。當(dāng)n≤5時(shí)，W(n)≤6，當(dāng)n=5，k=3時(shí)，可至多用6次比較完成。當(dāng)n>5時(shí)，估計(jì)1—4步所需的比較次數(shù)：1.

求各個(gè)5元組的中值，共需6×(n/5)=1.2n次比較；2.

求劃分元m*，遞歸代價(jià)為W(n/5)；3.

劃分過程中，B、C組元素與m*比較，共4×r≤0.4n次比較；4.

分治操作、遞歸調(diào)用元素個(gè)數(shù)至多為A、B、C或D、B、C三組元素，總數(shù)至多為7n/10，即比較次數(shù)不大于W(0.7n)。20綜合上述分析，有公式：為了解這個(gè)遞歸不等式，首先估計(jì)一個(gè)結(jié)果，然后用歸納法證明。展開3.9式：（公式3.9）21根據(jù)幾何級(jí)數(shù)估計(jì)：∴可以估計(jì)W(n)≤16n。 （公式3.10）然后用歸納法證明:1°1≤n≤5時(shí)，3.10式成立；2°假設(shè)，m<n時(shí)3.10式成立；3°對(duì)m=n（m>5），W(n)≤1.6n+W(0.2n)+W(0.7n)=1.6n+3.2n+11.2n=16n因此，W(n)≤16n確是3.9式的解，算法Select的最壞情形比較次數(shù)為O(n)階，當(dāng)然其平均情形性能更好。223.4.6討論1.

線性算法Select的設(shè)計(jì)過程體現(xiàn)了分治策略用來優(yōu)化算法設(shè)計(jì)的威力。設(shè)計(jì)者除了要掌握劃分、遞歸、平衡和合并等分治的基本要點(diǎn)之外，有時(shí)還需要輔以某些特殊的處理，往往能夠獲得出人意料的成功。2.

改進(jìn)算法的基本思路是對(duì)原有的算法進(jìn)行分析，在其次要部分付出一定代價(jià)，使得算法能在主要部分獲得收益。在選擇算法的設(shè)計(jì)過程中：設(shè)計(jì)一個(gè)較好的算法QSelect，它不是一個(gè)線性算法。判定算法的遞歸層數(shù)是影響算法時(shí)間性能的主要因素，而影響遞歸層數(shù)的主要因素是劃分的平衡。在尋找劃分元這個(gè)環(huán)節(jié)上，由原來的隨機(jī)選取改為復(fù)雜的方法，付出的代價(jià)是第1、2步的1.2n+W(0.2n)。23得到的收益有兩點(diǎn)：劃分的最壞情形代價(jià)由（n-1）減少到0.4n，遞歸代價(jià)由W(n-1)減少為W(0.7n)。事實(shí)上，收益大于付出，W(n)由θ(n2)階降為θ(n)階。3.

我們給出的“五元組”方法并不是唯一的成功途徑。例如V.Rratt，R.Rivest和R.Taijan設(shè)計(jì)的選擇算法的最壞情形比較次數(shù)達(dá)到W(n)≤5.43n，目前這方面的最好成果是W(n)≤2.95n。上述的高性能的算法的設(shè)計(jì)與分析主要具有理論上的價(jià)值，在實(shí)用中，它們往往有一些缺點(diǎn)，例如算法比較復(fù)雜、真正有效的n值比較大等等。4.

選擇問題在當(dāng)k值指定為中值時(shí)，稱為中值問題。中值問題是求一組數(shù)據(jù)的中間值，它不同于平均值。24中值問題和選擇問題之間有這樣的關(guān)系：表面上看，時(shí)比k取其它值算法應(yīng)花費(fèi)更大的代價(jià)，但中值問題畢竟是選擇問題的一個(gè)特例，它應(yīng)該比選擇問題的復(fù)雜度更低。不過中值問題復(fù)雜度改進(jìn)的余地已經(jīng)不大。已有的研究成果指出，對(duì)于奇數(shù)n，任何基于元素比較的中值算法至少需要1.5n–1.5次比較，進(jìn)一步的研究指出中值算法的復(fù)雜度下界為1.75n–logn，而后又改進(jìn)為1.8n，目前已知的最好的結(jié)果是：對(duì)于較大的n，至少需要2n次比較。這個(gè)值與最好的選擇算法的復(fù)雜度W(n)≤2.95n已相差不多。第三章完2526算法3.1簡(jiǎn)單的選擇算法Template<classElement>ElementQselect(Element[]L,intf,intl,intk){if(l==f)returnL[f];

inti=Partition(L,f,l);if(k<i–f+1)QSelect(L,f,i,k);elseQSelect(L,i+1,l,k-i+f-1);}返回27算法3.2Select

Template<classElement>ElementSelect(Element[]L,1,in