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

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

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

故A(n,1)=2*n(上式是一個遞推公式，每當(dāng)n-1便加2）M=2時，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時，類似的可以推出M=4時，A(n,4)的增長速度非常快，以至于沒有適當(dāng)?shù)臄?shù)學(xué)式子來表示這一函數(shù)。算法設(shè)計與分析>遞歸與分治7算法設(shè)計與分析>遞歸與分治1、證明A(1,1)=2因為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)因為n,

m>=1使用遞歸式(4)得A(n,1)=A(A(n-1,1),0)由公式(3)A(n,1)=A(n-1,1)+2由此式看出m=1時，n每降一階就增加2，一直降到n=1即A(1,1)共增加n個2，n個2相加和為2n所以A(n,1)=2n8算法設(shè)計與分析>遞歸與分治3、證明當(dāng)m=2時A(n,2)=2n由遞推式(4)A(n,2)=A(A(n-1,2),1),此時已經(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的降階會增長2的倍數(shù)，那么當(dāng)n降為1時即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ù)雜度分析中常遇到。對于通常所見到的正整數(shù)n，有α(n)≤4。但在理論上α(n)沒有上界，隨著n的增加，它以難以想象的慢速度趨向正無窮大。算法設(shè)計與分析>遞歸與分治9遞歸樹T(n)=3T(n/4)+O(n2)算法設(shè)計與分析>遞歸與分治10算法設(shè)計與分析>遞歸與分治1112補(bǔ)充：主方法（定理）求解這類遞推式的方法是主方法，主方法依賴于下面的主定理，使用主定理可直接得到遞推式的解。定理（主定理）：a≥1且b>1是常數(shù)，f(n)是一個函數(shù)，T(n)由如下的遞推式定義：T(n)=aT(n/b)+f(n)，式中，n/b指n/b或n/b，則T(n)有如下的漸近界：（1）若對于某常數(shù)?>0，有f(n)=O(nlogba-?)，則T(n)=(nlogba)；（2）若f(n)=(nlogba)，則T(n)=(nlogbalogn)；（3）若對于某常數(shù)?>0，有f(n)=(nlogba+?)，且對于某個常數(shù)c<1和所有足夠大的n，有af(n/b)≤cf(n)，則T(n)=(f(n))。T(n)=aT(n/b)+f(n)算法設(shè)計與分析>遞歸與分治13定理（主定理）：a≥1且b>1是常數(shù)，f(n)是一個函數(shù)，T(n)由如下的遞推式定義：T(n)=aT(n/b)+f(n)，式中，n/b指n/b或n/b，則T(n)有如下的漸近界：（1）若對于某常數(shù)?>0，有f(n)=O(nlogba-?)，則T(n)=(nlogba)；

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

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

子問題1的解

子問題2的解

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

原問題的解

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

//至少有2個元素

inti=(left+right)/2;

//取中點

MergeSort(a,left,i);

//對前半部分排序

MergeSort(a,i+1,right);

//對后半部分排序

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

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

Copy(a,b,left,right);

//復(fù)制回數(shù)組a

}}合并步，將有序表a[left,i]和a[i+1,right]合并到b[left,right]問題分解：規(guī)模為原來的一半；問題性質(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);

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

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

dividePintosmallersubinstancesP1,P2,...,Pk；//分解問題

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

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

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

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

算法設(shè)計與分析>遞歸與分治312.3二分搜索技術(shù)算法設(shè)計與分析>遞歸與分治問題描述：已知一個按非降次序排列的元素表a1,a2,…,an，判定某個給定元素x是否在該表中出現(xiàn)，若是，則找出該元素在表中的位置，并置于j，否則，置j為0。一般解決方法：從頭到尾查找一遍。a1a2a3a4…anx…成功與不成功的最壞情況下需O(n)次比較分析：如果n=1即只有一個元素，則只要比較這個元素和x就可以確定x是否在表中。因此這個問題滿足分治法的第一個適用條件分析：比較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即可。無論是在前面還是后面查找x，其方法都和在a中查找x一樣，只不過是查找的規(guī)?？s小了。這就說明了此問題滿足分治法的第二個和第三個適用條件。

分析：很顯然此問題分解出的子問題相互獨立，即在a[i]的前面或后面查找x是獨立的子問題，因此滿足分治法的適用條件。分析：該問題的規(guī)?？s小到一定的程度就可以容易地解決；該問題可以分解為若干個規(guī)模較小的相同問題;分解出的子問題的解可以合并為原問題的解；分解出的各個子問題是相互獨立的。算法設(shè)計與分析>遞歸與分治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)時間。算法在最壞情況下的計算時間復(fù)雜性為O(logn)。算法設(shè)計與分析>遞歸與分治332.8快速排序[算法思路]對A[p:r],按以下步驟進(jìn)行排序：(1)分解:取A中一元素為支點,將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)求解:通過遞歸調(diào)用分別對A[p:q-1]和A[q+1:r]排序。(3)合并:合并A[p:q-1],A[q],A[q+1:r]為A[p:r]。34算法設(shè)計與分析

>

遞歸與分治

>快速排序

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

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

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

//將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ī)選擇支點的快速排序]template<classT>voidrandomizedQuickSoft(Ta[],intp,intr){if(p<r){intq=randomizedPartition(a,p,r)randomizedQuickSort(a,p,q-1);//對左半段排序

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

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

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

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

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

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

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

遞歸與分治找數(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;

//支點元素是第j小個元素,左半部元素個數(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小個元素與快速排序算法不同,它只對子數(shù)組之一進(jìn)行遞歸處理。40執(zhí)行RandomizedPartiton，數(shù)組a[p:r]劃分成兩個子數(shù)組a[p:i]和a[i+1:r]，其中a[p:i]元素≤a[i+1:r]元素計算子數(shù)組a[p:i]中元素個數(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小個元素，返回a[i]遞歸循環(huán)。算法設(shè)計與分析>

遞歸與分治41

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

最壞情況:Tmax(n)=

(n2)(左半總為空)(等分點)

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

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

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

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

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時,max{|left|,|right|}<=3n/4442.4大整數(shù)的乘法[問題描述]設(shè)X,Y是兩個n位二進(jìn)制數(shù),求X*Y.45算法設(shè)計與分析>遞歸與分治一般方法：

O(n2)

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

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

Y=ABCDT(n)=O(n2)沒有改進(jìn)46[分析]這兩個算式更復(fù)雜一些，但它們僅需要3次n/2位乘法。{ac、bd和(a±b)(d±c)}[算法改進(jìn)]算法設(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個小于2n的二進(jìn)制整數(shù)，S=XY}functionMULT(X,Y,n)大數(shù)相乘的分治遞歸算法二進(jìn)制大整數(shù)乘法同樣可應(yīng)用于十進(jìn)制大整數(shù)的乘法.存放XY的符號存放三個乘積算法472.5Strassen矩陣相乘法[常規(guī)算法]設(shè)矩陣A=(aij)nn,B=(bij)nn,C=AB=(cij)nn

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

T(n)=O(n3)

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

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

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

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

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

遞歸與分治為了降低時間復(fù)雜度，必須減少乘法次數(shù)，其關(guān)鍵在于計算2個2階方陣的乘積時所用乘法次數(shù)能否少于8次。為此，Strassen提出了一種只用7次乘法運(yùn)算計算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è)計與分析>

遞歸與分治

得: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è)計與分析>

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

遞歸與分治54552k2k

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

遞歸與分治[算法思路]

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

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

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

56[算法分析]

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

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

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

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

遞歸與分治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{//此棋盤中無特殊方格

//用t號L型骨牌覆蓋右下角

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

//覆蓋其余方格

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

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

//覆蓋右上角子棋盤

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

//特殊方格在此棋盤中

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

else{//此棋盤中無特殊方格

//用t號骨牌覆蓋左下角

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è)計與分析>

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

遞歸與分治給定平面S上n個點,找其中的一對點,使得在

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

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

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

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

Cpairl(S1,d1);

//找到S1中最短距離

Cpairl(S2,d2);

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

//找到S1和S2中相鄰接點

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

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

得:T(n)=O(nlogn)

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

4)求一點在S1、另一點在S2中的最近點對

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

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