算法設(shè)計(jì)及分析 第二章ppt

第一章算法概述第二章遞歸與分治策略第三章動(dòng)態(tài)規(guī)劃第四章貪心算法第五章回朔法第六章分支限界法第七章概率算法算法設(shè)計(jì)與分析>目錄12算法設(shè)計(jì)與分析>遞歸與分治2.1遞歸的概念直接或間接地調(diào)用自身的算法稱為遞歸算法。由分治法產(chǎn)生的子問(wèn)題往往是原問(wèn)題的較小模式，為使用遞歸技術(shù)提供了方便。反復(fù)應(yīng)用分治手段，可以使子問(wèn)題與原問(wèn)題類型一致而其規(guī)模卻不斷縮小，最終使子問(wèn)題縮小到很容易直接求出其解，自然導(dǎo)致遞歸過(guò)程的產(chǎn)生。3算法設(shè)計(jì)與分析>遞歸與分治相關(guān)概念當(dāng)子問(wèn)題足夠大,需要遞歸求解時(shí),稱為遞歸情況;當(dāng)子問(wèn)題足夠小時(shí),不再需要遞歸時(shí),遞歸進(jìn)入“觸底”,進(jìn)入基本情況;用函數(shù)自身給出定義的函數(shù)稱為遞歸函數(shù);遞歸式是一個(gè)等式或不等式,它通過(guò)更小的輸入上的函數(shù)值來(lái)描述一個(gè)函數(shù).4遞歸函數(shù)的內(nèi)部執(zhí)行過(guò)程

（1）運(yùn)行開(kāi)始時(shí)，為遞歸調(diào)用建立一個(gè)工作棧，其結(jié)構(gòu)包括實(shí)參、局部變量和返回地址；（2）每次執(zhí)行遞歸調(diào)用之前，把遞歸函數(shù)的實(shí)參和局部變量的當(dāng)前值以及調(diào)用后的返回地址壓棧；（3）每次遞歸調(diào)用結(jié)束后，將棧頂元素出棧，使相應(yīng)的實(shí)參和局部變量恢復(fù)為調(diào)用前的值，然后轉(zhuǎn)向返回地址指定的位置繼續(xù)執(zhí)行算法設(shè)計(jì)與分析>遞歸與分治5算法設(shè)計(jì)與分析>遞歸與分治例2-3Ackerman函數(shù)當(dāng)一個(gè)函數(shù)及它的一個(gè)變量是由函數(shù)自身定義時(shí)，稱這個(gè)函數(shù)是雙遞歸函數(shù)。Ackerman函數(shù)A(n，m)定義如下：該變量是由函數(shù)自身定義6分析:A(n,m)的自變量m的每一個(gè)值都定義了一個(gè)單變量函數(shù)：M=0時(shí)，A(n,0)=n+2M=1時(shí)A(1,1)=2和A(n,1)=A(A(n-1,1),0)=A(n-1,1)+2，

故A(n,1)=2*n(上式是一個(gè)遞推公式，每當(dāng)n-1便加2）M=2時(shí)，A(1,2)=A(A(0,2),1)=A(1,1)=2A(n,2)=A(A(n-1,2),1)=2A(n-1,2)，故A(n,2)=2n

。M=3時(shí)，類似的可以推出M=4時(shí)，A(n,4)的增長(zhǎng)速度非常快，以至于沒(méi)有適當(dāng)?shù)臄?shù)學(xué)式子來(lái)表示這一函數(shù)。算法設(shè)計(jì)與分析>遞歸與分治7算法設(shè)計(jì)與分析>遞歸與分治1、證明A(1,1)=2因?yàn)閚,m>=1使用遞推式（4）得A(1,1)=A(A(0,1),0)由A(0,m)=1,故A(1,1）=A(1,0)由（1）式A(1,0)=2所以A(1,1)=22、證明A(n,1)=2n(n>=1)因?yàn)閚,

m>=1使用遞歸式(4)得A(n,1)=A(A(n-1,1),0)由公式(3)A(n,1)=A(n-1,1)+2由此式看出m=1時(shí)，n每降一階就增加2，一直降到n=1即A(1,1)共增加n個(gè)2，n個(gè)2相加和為2n所以A(n,1)=2n8算法設(shè)計(jì)與分析>遞歸與分治3、證明當(dāng)m=2時(shí)A(n,2)=2n由遞推式(4)A(n,2)=A(A(n-1,2),1),此時(shí)已經(jīng)演變?yōu)閙=1的情況，式中A(n-1,2)相當(dāng)于2節(jié)中的n的位置，因此利用2節(jié)的結(jié)論有A(n,2)=2A(n-1,2)可以看出隨著n的降階會(huì)增長(zhǎng)2的倍數(shù)，那么當(dāng)n降為1時(shí)即A(1,2)的情況如何呢？根據(jù)遞推式(4)有A(1,2)=A(A(0,2),1),再由公式(2)A(0,m)=1故A(1,2)=A(1,1)=2所以A(n,2)隨著n的降階每次乘2，共乘n次得A(n,2)=2n公式得證定義單變量的Ackerman函數(shù)A(n)為：A(n)=A(n,n)。定義其擬逆函數(shù)α(n)為：

α(n)=min{k｜A(k)≥n}。

即α(n)是使n≤A(k)成立的最小的k值。α(n)在復(fù)雜度分析中常遇到。對(duì)于通常所見(jiàn)到的正整數(shù)n，有α(n)≤4。但在理論上α(n)沒(méi)有上界，隨著n的增加，它以難以想象的慢速度趨向正無(wú)窮大。算法設(shè)計(jì)與分析>遞歸與分治9遞歸樹T(n)=3T(n/4)+O(n2)算法設(shè)計(jì)與分析>遞歸與分治10算法設(shè)計(jì)與分析>遞歸與分治1112補(bǔ)充：主方法（定理）求解這類遞推式的方法是主方法，主方法依賴于下面的主定理，使用主定理可直接得到遞推式的解。定理（主定理）：a≥1且b>1是常數(shù)，f(n)是一個(gè)函數(shù)，T(n)由如下的遞推式定義：T(n)=aT(n/b)+f(n)，式中，n/b指n/b或n/b，則T(n)有如下的漸近界：（1）若對(duì)于某常數(shù)?>0，有f(n)=O(nlogba-?)，則T(n)=(nlogba)；（2）若f(n)=(nlogba)，則T(n)=(nlogbalogn)；（3）若對(duì)于某常數(shù)?>0，有f(n)=(nlogba+?)，且對(duì)于某個(gè)常數(shù)c<1和所有足夠大的n，有af(n/b)≤cf(n)，則T(n)=(f(n))。T(n)=aT(n/b)+f(n)算法設(shè)計(jì)與分析>遞歸與分治13定理（主定理）：a≥1且b>1是常數(shù)，f(n)是一個(gè)函數(shù)，T(n)由如下的遞推式定義：T(n)=aT(n/b)+f(n)，式中，n/b指n/b或n/b，則T(n)有如下的漸近界：（1）若對(duì)于某常數(shù)?>0，有f(n)=O(nlogba-?)，則T(n)=(nlogba)；

舉例：T(n)=16T(n/4)+nT(n)=aT(n/b)+f(n)算法設(shè)計(jì)與分析>遞歸與分治14定理（主定理）：a≥1且b>1是常數(shù)，f(n)是一個(gè)函數(shù)，T(n)由如下的遞推式定義：T(n)=aT(n/b)+f(n)，式中，n/b指n/b或n/b，則T(n)有如下的漸近界：（2）若f(n)=(nlogba)，則T(n)=(nlogbalogn)；

舉例：T(n)=T(3n/7)+1T(n)=aT(n/b)+f(n)算法設(shè)計(jì)與分析>遞歸與分治15定理（主定理）：a≥1且b>1是常數(shù)，f(n)是一個(gè)函數(shù)，T(n)由如下的遞推式定義：T(n)=aT(n/b)+f(n)，式中，n/b指n/b或n/b，則T(n)有如下的漸近界：（3）若對(duì)于某常數(shù)?>0，有f(n)=(nlogba+?)，且對(duì)于某個(gè)常數(shù)c<1和所有足夠大的n，有af(n/b)≤cf(n)，則T(n)=(f(n))。

舉例：T(n)=3T(n/4)+nlognT(n)=aT(n/b)+f(n)算法設(shè)計(jì)與分析>遞歸與分治遞歸小結(jié)優(yōu)點(diǎn)：結(jié)構(gòu)清晰，可讀性強(qiáng)，而且容易用數(shù)學(xué)歸納法來(lái)證明算法的正確性，因此它為設(shè)計(jì)算法、調(diào)試程序帶來(lái)很大方便。缺點(diǎn)：遞歸算法的運(yùn)行效率較低，無(wú)論是耗費(fèi)的計(jì)算時(shí)間還是占用的存儲(chǔ)空間都比非遞歸算法要多。算法設(shè)計(jì)與分析>遞歸與分治16解決方法：在遞歸算法中消除遞歸調(diào)用，使其轉(zhuǎn)化為非遞歸算法。1、采用一個(gè)用戶定義的棧來(lái)模擬系統(tǒng)的遞歸調(diào)用工作棧。該方法通用性強(qiáng)，但本質(zhì)上還是遞歸，只不過(guò)人工做了本來(lái)由編譯器做的事情，優(yōu)化效果不明顯。2、用遞推來(lái)實(shí)現(xiàn)遞歸函數(shù)。3、通過(guò)變換能將一些遞歸轉(zhuǎn)化為尾遞歸，從而迭代求出結(jié)果。后兩種方法在時(shí)空復(fù)雜度上均有較大改善，但其適用范圍有限。算法設(shè)計(jì)與分析>遞歸與分治1718尾遞歸是在遞歸調(diào)用時(shí)“積累”之前調(diào)用的結(jié)果，并將其傳入下一次遞歸調(diào)用中,將遞歸方法中的需要的“所有狀態(tài)”通過(guò)方法的參數(shù)傳入下一次調(diào)用中.算法設(shè)計(jì)與分析>遞歸與分治尾遞歸只會(huì)占用恒量的內(nèi)存,形式上只要最后一個(gè)return語(yǔ)句是單純函數(shù)就可以2.2分治法的基本思想算法設(shè)計(jì)與分析>遞歸與分治19將一個(gè)規(guī)模為n的問(wèn)題分解為k個(gè)規(guī)模較小的子問(wèn)題，這些子問(wèn)題互相獨(dú)立且與原問(wèn)題相同。對(duì)這k個(gè)子問(wèn)題分別求解。如果子問(wèn)題的規(guī)模仍然不夠小，則再劃分為k個(gè)子問(wèn)題，如此遞歸的進(jìn)行下去，直到問(wèn)題規(guī)模足夠小，很容易求出其解為止。將求出的小規(guī)模的問(wèn)題的解合并為一個(gè)更大規(guī)模的問(wèn)題的解，自底向上逐步求出原來(lái)問(wèn)題的解。20

子問(wèn)題1的規(guī)模是n/2

子問(wèn)題1的解

子問(wèn)題2的解

子問(wèn)題2的規(guī)模是n/2

原問(wèn)題的解

原問(wèn)題的規(guī)模是n算法設(shè)計(jì)與分析>遞歸與分治21算法設(shè)計(jì)與分析>遞歸與分治問(wèn)題（N個(gè)輸入）子問(wèn)題1子問(wèn)題2子問(wèn)題K…子問(wèn)題1子問(wèn)題2子問(wèn)題k…相同類型合并解分治法要求分解成同類子問(wèn)題，并允許不斷分解，使問(wèn)題規(guī)模逐步減小，最終可用已知的方法求解足夠小的問(wèn)題。22算法設(shè)計(jì)與分析>遞歸與分治舉例：二路歸并排序分解過(guò)程：對(duì)任意長(zhǎng)度為n的序列排序，首先將問(wèn)題不斷分解，直至問(wèn)題可直接求解。長(zhǎng)度為n的序列分解為2個(gè)n/2的子序列，依次循環(huán)，直至分解為n個(gè)長(zhǎng)度為1的序列，顯然長(zhǎng)度為1的序列是有序表。合并過(guò)程：將已排序的的子序列不斷合并，形成長(zhǎng)度為n的排序序列。然后反復(fù)進(jìn)行兩兩歸并為n/2個(gè)有序表；再對(duì)n/2個(gè)有序表兩兩歸并，循環(huán)直到得到長(zhǎng)度為n的有序線性表。23算法設(shè)計(jì)與分析>遞歸與分治template<classType>voidMergeSort(Typea[],intleft,intright){if(left<right){

//至少有2個(gè)元素

inti=(left+right)/2;

//取中點(diǎn)

MergeSort(a,left,i);

//對(duì)前半部分排序

MergeSort(a,i+1,right);

//對(duì)后半部分排序

Merge(a,b,left,i,right);

//合并到數(shù)組b

Copy(a,b,left,right);

//復(fù)制回?cái)?shù)組a

}}合并步，將有序表a[left,i]和a[i+1,right]合并到b[left,right]問(wèn)題分解：規(guī)模為原來(lái)的一半；問(wèn)題性質(zhì)不變。24template<classType>voidMergeSort(Typea[],intleft,intright){if(left<right){

inti=(left+right)/2;

MergeSort(a,left,i);

MergeSort(a,i+1,right);

Merge(a,b,left,i,right);

Copy(a,b,left,right);

}}分析：二路歸并排序的時(shí)空復(fù)雜性算法設(shè)計(jì)與分析>遞歸與分治時(shí)間復(fù)雜度T(n)cT(n/2)T(n/2)O(n)O(n)voidMerge(Typec[],Typed[],inti,intm,intr){intla,lb,lc;la=i;lb=m+1;lc=i;while(la<=m&&lb<=n){if(c[la]<c[lb])d[lc++]=c[la++];elsed[lc++]=c[lb++];}while(la<=m)d[lc++]=c[la++];

while(lb<=n)d[lc++]=c[lb++];}25二路歸并排序算法存在以下遞推式：解此遞歸方程，二路歸并排序的時(shí)間復(fù)雜度是O(nlogn)。二路歸并排序其空間復(fù)雜性為O(n)。算法設(shè)計(jì)與分析>遞歸與分治26算法設(shè)計(jì)與分析>遞歸與分治總結(jié)：分治法的適用條件分治法所能解決的問(wèn)題一般具有以下特征：該問(wèn)題規(guī)模縮小到一定的程度就可以容易地解決；該問(wèn)題可以分解為若干個(gè)規(guī)模較小的相同子問(wèn)題，即該問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì)；利用該問(wèn)題分解出的子問(wèn)題的解可以合并為該問(wèn)題的解；該問(wèn)題所分解出的各個(gè)子問(wèn)題是相互獨(dú)立的，即子問(wèn)題之間不包含公共的子問(wèn)題。應(yīng)用分治法的前提，它也是大多數(shù)問(wèn)題可以滿足的，此特征反映了遞歸思想的應(yīng)用。關(guān)鍵特征，能否利用分治法完全取決于問(wèn)題是否具有第四條特征，如果具備了第一條和第二條特征，而不具備第四條特征，則可以考慮貪心法或動(dòng)態(tài)規(guī)劃法。27算法設(shè)計(jì)與分析>遞歸與分治分治法的基本步驟:劃分：把規(guī)模為n的原問(wèn)題劃分為k個(gè)規(guī)模較小的子問(wèn)題，并盡量使這k個(gè)子問(wèn)題的規(guī)模大致相同。求解子問(wèn)題：各子問(wèn)題的解法與原問(wèn)題的解法通常是相同的，可以用遞歸的方法求解各個(gè)子問(wèn)題，有時(shí)也可用循環(huán)來(lái)實(shí)現(xiàn)。合并：把各個(gè)子問(wèn)題的解合并起來(lái)。divide-and-conquer(P){

if(|P|<=n0)adhoc(P);//解決小規(guī)模的問(wèn)題

dividePintosmallersubinstancesP1,P2,...,Pk；//分解問(wèn)題

for(i=1,i<=k,i++)yi=divide-and-conquer(Pi);//遞歸的解各子問(wèn)題

returnmerge(y1,...,yk);//將各子問(wèn)題的解合并為原問(wèn)題的解

}分治法的基本步驟算法設(shè)計(jì)與分析>遞歸與分治28在用分治法設(shè)計(jì)算法時(shí)，最好使子問(wèn)題的規(guī)模大致相同，即，將一個(gè)問(wèn)題分成大小相等的k個(gè)子問(wèn)題（許多問(wèn)題取k=2）。使子問(wèn)題規(guī)模大致相等的做法是出自一種平衡子問(wèn)題的思想，這通常比子問(wèn)題規(guī)模不等的做法要好。|P|問(wèn)題P的規(guī)模n0為閥值adhoc(P)基本子算法29分治法的復(fù)雜性分析從一般設(shè)計(jì)模式看，用分治法設(shè)計(jì)的程序通常是一個(gè)遞歸算法。分治法將規(guī)模為n的問(wèn)題分成k個(gè)規(guī)模為n/m的子問(wèn)題：設(shè)n0=1,且adhoc解問(wèn)題耗費(fèi)1個(gè)單位時(shí)間。再設(shè)將原問(wèn)題分解為k個(gè)子問(wèn)題以及用merge將k個(gè)子問(wèn)題的解合并為原問(wèn)題的解需用f

(n)個(gè)單位時(shí)間。用T(n)（遞歸方程）表示該分治法求解規(guī)模為|P|=n的問(wèn)題所需的計(jì)算時(shí)間：算法設(shè)計(jì)與分析>遞歸與分治30通過(guò)迭代法求得方程解：基本子問(wèn)題花費(fèi)時(shí)間合并步花費(fèi)時(shí)間

算法設(shè)計(jì)與分析>遞歸與分治312.3二分搜索技術(shù)算法設(shè)計(jì)與分析>遞歸與分治問(wèn)題描述：已知一個(gè)按非降次序排列的元素表a1,a2,…,an，判定某個(gè)給定元素x是否在該表中出現(xiàn)，若是，則找出該元素在表中的位置，并置于j，否則，置j為0。一般解決方法：從頭到尾查找一遍。a1a2a3a4…anx…成功與不成功的最壞情況下需O(n)次比較分析：如果n=1即只有一個(gè)元素，則只要比較這個(gè)元素和x就可以確定x是否在表中。因此這個(gè)問(wèn)題滿足分治法的第一個(gè)適用條件分析：比較x和a的中間元素a[mid]，若x=a[mid]，則x在L中的位置就是mid；如果x<a[mid]，由于a是遞增排序的，因此假如x在a中的話，x必然排在a[mid]的前面，所以我們只要在a[mid]的前面查找x即可；如果x>a[i]，同理我們只要在a[mid]的后面查找x即可。無(wú)論是在前面還是后面查找x，其方法都和在a中查找x一樣，只不過(guò)是查找的規(guī)模縮小了。這就說(shuō)明了此問(wèn)題滿足分治法的第二個(gè)和第三個(gè)適用條件。

分析：很顯然此問(wèn)題分解出的子問(wèn)題相互獨(dú)立，即在a[i]的前面或后面查找x是獨(dú)立的子問(wèn)題，因此滿足分治法的適用條件。分析：該問(wèn)題的規(guī)?？s小到一定的程度就可以容易地解決；該問(wèn)題可以分解為若干個(gè)規(guī)模較小的相同問(wèn)題;分解出的子問(wèn)題的解可以合并為原問(wèn)題的解；分解出的各個(gè)子問(wèn)題是相互獨(dú)立的。算法設(shè)計(jì)與分析>遞歸與分治32二分搜索算法：template<classType>intBinarySearch(Typea[],constType&x,intl,intr){while(r>=l){intm=(l+r)/2;if(x==a[m])returnm;if(x<a[m])r=m-1;elsel=m+1;}return-1;}算法復(fù)雜度分析：每執(zhí)行一次算法的while循環(huán)，待搜索數(shù)組的大小減少一半。在最壞情況下，while循環(huán)被執(zhí)行O(logn)次，循環(huán)體內(nèi)運(yùn)算需要O(1)時(shí)間。算法在最壞情況下的計(jì)算時(shí)間復(fù)雜性為O(logn)。算法設(shè)計(jì)與分析>遞歸與分治332.8快速排序[算法思路]對(duì)A[p:r],按以下步驟進(jìn)行排序：(1)分解:取A中一元素為支點(diǎn),將A[p:r]分成3段:A[p:q-1],A[q],A[q+1:r],其中A[p:q-1]中元素A[q],A[q+1:r]中元素A[q];(2)求解:通過(guò)遞歸調(diào)用分別對(duì)A[p:q-1]和A[q+1:r]排序。(3)合并:合并A[p:q-1],A[q],A[q+1:r]為A[p:r]。34算法設(shè)計(jì)與分析

>

遞歸與分治

>快速排序

得:Tmax(n)=O(n2)[快速排序算法]template<classT>voidQuickSoft(T

a[],intp,intr){if(p<r){intq=Partition(a,p,r)QuickSort(a,p,q-1);//對(duì)左半段排序

QuickSoft(a,q+1,r);//對(duì)右半段排序template<classT>intPartion(Ta[],intp,intr){inti=p;j=r+1;tx=a[p]；//取支點(diǎn)

//將x的元素交換到左邊

//將x的元素交換到右邊

while(true){while(a[++i]<x)；

while(a[--j]>x)；

if(i>=j)break;swap(a[i],a[j]);}a[p]=a[j]；

a[j]=x;returnj}

Tmin(n)=O(1)n<=12T(n/2)+O(n)n>1

得:Tmin(n)=O(nlogn)[復(fù)雜性分析]

Tmax(n)=O(1)n<=1T(n-1)+O(n)n>135[隨機(jī)選擇支點(diǎn)的快速排序]template<classT>voidrandomizedQuickSoft(Ta[],intp,intr){if(p<r){intq=randomizedPartition(a,p,r)randomizedQuickSort(a,p,q-1);//對(duì)左半段排序

randomizedQuickSoft(a,q+1,r);//對(duì)右半段排序

}}算法設(shè)計(jì)與分析>

遞歸與分治>快速排序template<classT>intrandomizedPartition(Ta[],intp,intr){inti=random(p,r)swap(a[i],a[p])returnPartition(a,p,r)36快速排序算法性能取決于劃分的對(duì)稱性2.9線性時(shí)間選擇[問(wèn)題陳述]

求n個(gè)元素中的第k小元素.給定線性序集中n個(gè)不同的元素和一個(gè)整數(shù)k，1?k?n要求找出這n個(gè)元素中第k小的元素，即如果將這n個(gè)元素依其線性序排列時(shí)，排在第k個(gè)位置的元素即為我們要找的元素。當(dāng)k=1時(shí),找最小元;當(dāng)k=n時(shí),找最大元素;當(dāng)k=(n+1)/2時(shí),找中位數(shù).37算法設(shè)計(jì)與分析>

遞歸與分治38算法設(shè)計(jì)與分析>

遞歸與分治[算法思路]模仿快速排序,對(duì)輸入數(shù)組A進(jìn)行二分,使子數(shù)組A1的元素

A2中的元素,分點(diǎn)J由隨機(jī)數(shù)產(chǎn)生.若KJ,則K為A1的第K小元,若K>J,則K為A2的第K-J小元.39算法設(shè)計(jì)與分析>

遞歸與分治找數(shù)組a[0:n-1]第k小元素調(diào)用RandomizedSelect(a,0,n-1,k)template<classT>TRandomizedSelect(a[],intp,intr,intk){if(p==r)returna[p];

inti=RandomizedPartition(a,p,r);j=i-p+1;

//支點(diǎn)元素是第j小個(gè)元素,左半部元素個(gè)數(shù)

ifk==jreturnA[i];

if(k<j)returnRandomizedSelect(a,p,i-1,k);else

returnRandomizedSelect(a,i+1,r,k-j);

}p,r數(shù)組范圍K:第k小個(gè)元素與快速排序算法不同,它只對(duì)子數(shù)組之一進(jìn)行遞歸處理。40執(zhí)行RandomizedPartiton，數(shù)組a[p:r]劃分成兩個(gè)子數(shù)組a[p:i]和a[i+1:r]，其中a[p:i]元素≤a[i+1:r]元素計(jì)算子數(shù)組a[p:i]中元素個(gè)數(shù)j如果k<j,則a[p:i]中第k小元素落在子數(shù)組a[p:i]中;如果k>j,則要找的第k小元素落在子數(shù)組a[i+1:r]中,要找的a[p:r]中第k小的元素是a[i+1:r]中的第k-j小的元素。如果k=j,找到第k小個(gè)元素，返回a[i]遞歸循環(huán)。算法設(shè)計(jì)與分析>

遞歸與分治41

Tmin(n)=dT(n)=T(n/2)+cn[分析]

最壞情況:Tmax(n)=

(n2)(左半總為空)(等分點(diǎn))

得:Tmin(n)=(n)算法設(shè)計(jì)與分析>

遞歸與分治最壞情況下的選擇算法分析42算法設(shè)計(jì)與分析>

遞歸與分治算法RandomizedSelect需要Ω(n2)計(jì)算時(shí)間。例如在找最小元素時(shí)，總是在最大元素處劃分。(n-1)+(n-2)+…+1=n2算法RandomizedSelect不穩(wěn)定的原因：由于隨機(jī)劃分函數(shù)使用了一個(gè)隨機(jī)數(shù)產(chǎn)生器Random,產(chǎn)生p和r之間的一個(gè)隨機(jī)整數(shù)，因此產(chǎn)生的劃分基準(zhǔn)是隨機(jī)的?？梢宰C明，算法可以在O(n)平均時(shí)間內(nèi)找出n個(gè)輸入元素中的第k小元素。43[算法思路](中間的中間):將A中元素分為n/r組,除最后一組外,每組元素為r個(gè),用任意排序算法排序,取出每組的中位數(shù),對(duì)n/r個(gè)中位數(shù)遞歸調(diào)用,找到中位數(shù),以該元素作為劃分基準(zhǔn).算法設(shè)計(jì)與分析>

遞歸與分治xtemplate<classT>TSelect(Ta[],intp,intr,intk){if(r-p<75){用簡(jiǎn)單排序法排序；

returna[p+k-1]}；

for(inti=0;i<=(r-p-4)/5;i++)

將a[p+5*i]至a[p+5*i-4]的第3小元素與a[p+i]交換位置；

//找中位數(shù)的中位數(shù)

Tx=Select(a,p,p+(r-p-4)/5,(r-p-4)/10);inti=Partition(a,p,r,x),j=i-p+1;if(k<=j)returnSelect(a,p,i,k)elsereturnSelect(a,i+1,r,k-j)}最壞情況下的選擇算法:[算法分析]

T(n)=得:T(n)=O(n)c1n<75c2n+T(n/5)+T(3n/4)定理:若r=5且數(shù)組中元素互不相同,則n>75時(shí),max{|left|,|right|}<=3n/4442.4大整數(shù)的乘法[問(wèn)題描述]設(shè)X,Y是兩個(gè)n位二進(jìn)制數(shù),求X*Y.45算法設(shè)計(jì)與分析>遞歸與分治一般方法：

O(n2)

效率太低！分治法：復(fù)雜性分析：

n/2位n/2位n/2位n/2位X=

Y=ABCDT(n)=O(n2)沒(méi)有改進(jìn)46[分析]這兩個(gè)算式更復(fù)雜一些，但它們僅需要3次n/2位乘法。{ac、bd和(a±b)(d±c)}[算法改進(jìn)]算法設(shè)計(jì)與分析>遞歸與分治為了降低時(shí)間復(fù)雜度，必須減少乘法的次數(shù)。為此，把XY寫成另外的形式：XY=ac2n+((a-b)(d-c)+ac+bd)2n/2+bd或XY=ac2n+((a+b)(c+d)-ac-bd)2n/2+bd結(jié)論：T(n)=O(nlog3)=O(n1.59)較大的改進(jìn){S=SIGN(X)*SIGN(Y)；

X:=ABS(X)；Y:=ABS(Y)；

ifn=lthenif(X=1)and(Y=1)thenreturn(S)elsereturn(0)else{A:=X的左邊n/2位；

B:=X的右邊n/2位；

C:=Y的左邊n/2位；

D:=Y的右邊n/2位；

m1:=MULT(A，C，n/2)；

m2:=MULT(A-B,D-C，n/2)；

m3:=MULT(B，D，n/2)；

S:=S*(m1*2n+(m1+m2+m3)*2n/2+m3)；

return(S)}}{X,Y為2個(gè)小于2n的二進(jìn)制整數(shù)，S=XY}functionMULT(X,Y,n)大數(shù)相乘的分治遞歸算法二進(jìn)制大整數(shù)乘法同樣可應(yīng)用于十進(jìn)制大整數(shù)的乘法.存放XY的符號(hào)存放三個(gè)乘積算法472.5Strassen矩陣相乘法[常規(guī)算法]設(shè)矩陣A=(aij)nn,B=(bij)nn,C=AB=(cij)nn

計(jì)算C共需nn2個(gè)乘法,n2(n-1)個(gè)加法.

T(n)=O(n3)

算法設(shè)計(jì)與分析>

遞歸與分治48如果依此定義來(lái)計(jì)算矩陣A和B的乘積矩陣C，則每計(jì)算C的一個(gè)元素C[i,j]，需要做n次乘法和n-1次加法。49算法設(shè)計(jì)與分析>

遞歸與分治C11=A11B11+A12B21C12=A11B12+A12B22C21=A21B11+A22B21C22=A21B12+A22B22首先假定n是2（n=2k）的冪，如果相乘的兩矩陣A和B不是方陣，可以通過(guò)適當(dāng)添加全零行和全零列，使之成為行列數(shù)為2的冪的方陣。使用分治法，將矩陣A、B和C中每一矩陣都分塊成4個(gè)大小相等的子矩陣，每個(gè)子矩陣都是n/2×n/2的方陣。由此可將方程C=A×B重寫為：[算法思路]

50算法設(shè)計(jì)與分析>

遞歸與分治如果n=2，則兩個(gè)2階方陣的乘積可以直接計(jì)算出來(lái)，共需8次乘法和4次加法。當(dāng)子矩陣的階大于2時(shí)，可以繼續(xù)將子矩陣分塊，直到子矩陣的階降為2。這樣，就產(chǎn)生了一個(gè)分治降階的遞歸算法。依此算法，計(jì)算2個(gè)n階方陣的乘積轉(zhuǎn)化為計(jì)算8個(gè)n/2階方陣的乘積和4個(gè)n/2階方陣的加法。2個(gè)n/2×n/2矩陣的加法顯然可以在c*n2/4(O(n2))時(shí)間內(nèi)完成，這里c是一個(gè)常數(shù)。上述分治法的計(jì)算時(shí)間耗費(fèi)T(n)的遞歸方程滿足：T(n)=O(n3)沒(méi)有改進(jìn)，原因是沒(méi)有減少矩陣乘法次數(shù)。51算法設(shè)計(jì)與分析>

遞歸與分治為了降低時(shí)間復(fù)雜度，必須減少乘法次數(shù)，其關(guān)鍵在于計(jì)算2個(gè)2階方陣的乘積時(shí)所用乘法次數(shù)能否少于8次。為此，Strassen提出了一種只用7次乘法運(yùn)算計(jì)算2階方陣乘積的方法（但增加了加/減法次數(shù)）：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)C11=M5+M4-M2+M6C12=M1+M2C21=M3+M4C22=M5+M1-M3-M7算法設(shè)計(jì)與分析>

遞歸與分治

得:T(n)=O(nlog7)=O(n2.81)[分析]

52做了這7次乘法后，再做若干次加/減法就可以得到：較大的改進(jìn)procedureSTRASSEN(n,A,B,C)；

{ifn=2thenMATRIX_MULTIPLY(A,B,C)else{將矩陣A和B分塊；

STRASSEN(n/2，A11，B12-B22，M1)；

STRASSEN(h/2，A11+A12，B22，M2)；

STRASSEN(n/2，A21+A22，B11，M3)；

STRASSEN(n/2，A22，B21-B11，M4)；

STRASSEN(n/2，A11+A22，B11+B22，M5)STRASSEN(n/2，A12-A22，B21+B22，M6)；

STRASSEN(n/2，A11+A21，B11+B12，M7)C:=矩陣相乘Strassen算法算法算法設(shè)計(jì)與分析>

遞歸與分治53[問(wèn)題陳述]在一個(gè)2k2k個(gè)方格組成的棋盤中,恰有一方格殘缺,殘缺方格的位置有22k種。故對(duì)任何k≥0,殘缺棋盤有22k種.要求用L型骨牌覆蓋殘缺棋盤上的所有方格且任何2個(gè)L型骨牌不得重疊覆蓋。2.6棋盤覆蓋算法設(shè)計(jì)與分析>

遞歸與分治54552k2k

的棋盤覆蓋中，用到的骨牌數(shù)為(4k-1)/3算法設(shè)計(jì)與分析>

遞歸與分治[算法思路]

當(dāng)k>0時(shí),將2k2k棋盤分割為4個(gè)2k-12k-1子棋盤,殘缺方格必位于4個(gè)子棋盤之一.其余3個(gè)子棋盤中無(wú)殘缺方格.

用一個(gè)L型骨牌覆蓋這3個(gè)較小棋盤的結(jié)合處.這3個(gè)子棋盤上被L型骨牌覆蓋的方格就成為該棋盤上的殘缺方格,原問(wèn)題轉(zhuǎn)化為4個(gè)較小規(guī)模的棋盤覆蓋問(wèn)題。遞歸地使用這種分割，直至棋盤簡(jiǎn)化為11棋盤.算法設(shè)計(jì)與分析>

遞歸與分治為此將剩余3棋盤轉(zhuǎn)化為殘缺棋盤:

56[算法分析]

設(shè)T(k)為覆蓋2k2k殘缺棋盤的時(shí)間,

當(dāng)k=0時(shí)覆蓋它需要常數(shù)時(shí)間O(1).當(dāng)k>0時(shí),測(cè)試哪個(gè)子棋盤殘缺以及形成3個(gè)殘缺子棋盤需要O(1),覆蓋4個(gè)殘缺子棋盤需四次遞歸調(diào)用,共需時(shí)間4T(k-1).

T(k)=O(1)4T(k-1)+O(1)

迭代法解得:T(k)=(4k)與所需骨牌數(shù)同階算法設(shè)計(jì)與分析>

遞歸與分治57voidChessBoard(inttr,inttc,intdr,intdc,intsize){if(size==1)return；

intt=tile++，//L型骨牌數(shù)

s=size／2；//分割棋盤

//覆蓋左上角子棋盤

if(dr<tr+s&&dc<tc+S)

//特殊方格在此棋盤中

ChessBoard(tr,tc,dr,dc,S)；

else{//此棋盤中無(wú)特殊方格

//用t號(hào)L型骨牌覆蓋右下角

Board[tr+s-1][tc+s-1]=t；

//覆蓋其余方格

Chessboard(tr，tc，tr+s-1，tc+s-l，s)；}算法設(shè)計(jì)與分析>

遞歸與分治tr:左上角方格行tc:左上角方格列dr:殘缺方格行dc:殘缺方格列size:棋盤行數(shù)Board:為全局變量二維數(shù)組表示棋盤58

//覆蓋右上角子棋盤

if(dr<=tr+s&&dc>=tc+S)

//特殊方格在此棋盤中

ChessBoard(tr，tc+s，dr，dc，S)；

else{//此棋盤中無(wú)特殊方格

//用t號(hào)骨牌覆蓋左下角

Board[tr+s-1][tc+s]=t；

//覆蓋其余方格

Chessboard(tr，tc+s，tr+s-1，tc+s，s)；}

………………...voidoutputBoard(intsize){forinti=0;i<size;i++){forintj=0;j<size;j++)；

cout<<setw(5)<<board[i][j];cout<<endl;}}算法設(shè)計(jì)與分析>

遞歸與分治5960算法設(shè)計(jì)與分析>

遞歸與分治給定平面S上n個(gè)點(diǎn),找其中的一對(duì)點(diǎn),使得在

n(n-1)/2個(gè)點(diǎn)對(duì)中,該點(diǎn)對(duì)的距離最小。2.10最接近點(diǎn)對(duì)問(wèn)題[問(wèn)題描述]簡(jiǎn)化問(wèn)題（一維問(wèn)題）為了使問(wèn)題易于理解和分析，先來(lái)考慮一維的情形。此時(shí)，S中的n個(gè)點(diǎn)退化為x軸上的n個(gè)實(shí)數(shù)x1,x2,…,xn。最接近點(diǎn)對(duì)即為這n個(gè)實(shí)數(shù)中相差最小的2個(gè)實(shí)數(shù)。61算法設(shè)計(jì)與分析>

遞歸與分治假設(shè)我們用x軸上某個(gè)點(diǎn)m將S劃分為2個(gè)子集S1和S2，基于平衡子問(wèn)題的思想，用S中各點(diǎn)坐標(biāo)的中位數(shù)來(lái)作分割點(diǎn)。遞歸地在S1和S2上找出其最接近點(diǎn)對(duì){p1,p2}和{q1,q2}，并設(shè)d=min{|p1-p2|,|q1-q2|}，S中的最接近點(diǎn)對(duì)或者是{p1,p2}，或者是{q1,q2}，或者是某個(gè){p3,q3}，其中p3∈S1且q3∈S2。能否在線性時(shí)間內(nèi)找到p3,q3？62算法設(shè)計(jì)與分析>

遞歸與分治如果S的最接近點(diǎn)對(duì)是{p3,q3}，即|p3-q3|<d，則p3和q3兩者與m的距離不超過(guò)d，即p3∈(m-d,m]，q3∈(m,m+d]。由于在S1中，每個(gè)長(zhǎng)度為d的半閉區(qū)間至多包含一個(gè)點(diǎn)（否則必有兩點(diǎn)距離小于d），并且m是S1和S2的分割點(diǎn)，因此(m-d,m]中至多包含S中的一個(gè)點(diǎn)。由圖可以看出，如果(m-d,m]中有S中的點(diǎn)，則此點(diǎn)就是S1中最大點(diǎn)。同理,如果(m,m+d]中有S中的點(diǎn)，則此點(diǎn)就是S2中最小點(diǎn)。用線性時(shí)間就能找到區(qū)間(m-d,m]和(m,m+d]中所有點(diǎn)，即p3和q3。用線性時(shí)間就可以將S1的解和S2的解合并成為S的解。能否在線性時(shí)間內(nèi)找到p3,q3？63算法設(shè)計(jì)與分析>

遞歸與分治BoolCpairl(S,d){n=|S|;if(n<2){d=MAX;returnfalse;}m=S中各點(diǎn)坐標(biāo)的中位數(shù);

Cpairl(S1,d1);

//找到S1中最短距離

Cpairl(S2,d2);

//找到S2中最短距離p=max(S1);q=min(S2);

//找到S1和S2中相鄰接點(diǎn)

d=min(d1,d2,q-p);returntrue;}

T(n)=O(1)T(n)=2T(n/2)+O(n)

得:T(n)=O(nlogn)

1)n較小時(shí)直接求(n=2).2)將S上的n個(gè)點(diǎn)分成大致相等的2個(gè)子集S1和S23)分別求S1和S2中的最接近點(diǎn)對(duì)

4)求一點(diǎn)在S1、另一點(diǎn)在S2中的最近點(diǎn)對(duì)

5)從上述三對(duì)點(diǎn)中找距離最近的一對(duì).算法設(shè)計(jì)與分析>

遞歸與分治[算法思路]64二維平面