分治技術(shù)課件

分治技術(shù)

3.1分治策略的思想

3.2大整數(shù)乘法

3.3矩陣相乘的Strassen算法

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

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

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

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

設(shè)Х和Ｙ是兩個n位的二進(jìn)制數(shù)，按傳統(tǒng)方法計算乘積Х·Ｙ，需要O(n2)次位運(yùn)算。為簡化問題，設(shè)n=2k，k為正整數(shù)。當(dāng)n=1時，計算Х·Ｙ就是一次位乘。對Х、Ｙ進(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

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

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

（公式3.1）

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

（公式3.4）（公式3.3）

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

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

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

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

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

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

把n階矩陣A，B劃分為8個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個子矩陣，也是可以的。3.

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

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

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

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

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

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

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

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

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

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

分治操作、遞歸調(diào)用元素個數(shù)至多為A、B、C或D、B、C三組元素，總數(shù)至多為7n/10，即比較次數(shù)不大于W(0.7n)。20綜合上述分析，有公式：為了解這個遞歸不等式，首先估計一個結(jié)果，然后用歸納法證明。展開3.9式：（公式3.9）21根據(jù)幾何級數(shù)估計：∴可以估計W(n)≤16n。 （公式3.10）然后用歸納法證明:1°1≤n≤5時，3.10式成立；2°假設(shè)，m<n時3.10式成立；3°對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è)計過程體現(xiàn)了分治策略用來優(yōu)化算法設(shè)計的威力。設(shè)計者除了要掌握劃分、遞歸、平衡和合并等分治的基本要點(diǎn)之外，有時還需要輔以某些特殊的處理，往往能夠獲得出人意料的成功。2.

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

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

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