算法分析與設(shè)計分治法課件

算法分析與設(shè)計分治法ppt課件41、實際上，我們想要的不是針對犯罪的法律，而是針對瘋狂的法律?！R克·吐溫42、法律的力量應(yīng)當跟隨著公民，就像影子跟隨著身體一樣?！惪ɡ麃?3、法律和制度必須跟上人類思想進步?！芨ミd44、人類受制于法律，法律受制于情理?！小じ焕?5、法律的制定是為了保證每一個人自由發(fā)揮自己的才能，而不是為了束縛他的才能?！_伯斯庇爾算法分析與設(shè)計分治法ppt課件算法分析與設(shè)計分治法ppt課件41、實際上，我們想要的不是針對犯罪的法律，而是針對瘋狂的法律。——馬克·吐溫42、法律的力量應(yīng)當跟隨著公民，就像影子跟隨著身體一樣。——貝卡利亞43、法律和制度必須跟上人類思想進步?！芨ミd44、人類受制于法律，法律受制于情理。——托·富勒45、法律的制定是為了保證每一個人自由發(fā)揮自己的才能，而不是為了束縛他的才能。——羅伯斯庇爾算法分析與設(shè)計第二章分治法第二章分治法什么是分治法？二分檢索找最大和最小元素歸并分類快速分類選擇問題斯特拉森矩陣乘法分治策略DANDC的計算時間倘若所分成的兩個子問題的輸入規(guī)模大致相等，則分治策略DANDC的計算時間可表示為：T(n)=g(n) n足夠小2T(n/2)+f(n) 否則說明：T(n)是輸入規(guī)模為n的分治策略的計算時間g(n)是對足夠小的輸入規(guī)模能直接計算出答案的時間f(n)是COMBINE解合成原問題的計算時間2.2二分檢索問題描述已知一個按非降次序排列的元素表a1,a2,…,an，判定某個給定元素x是否在該表中出現(xiàn)，若是，則找出該元素在表中的位置，并置于j，否則，置j為0。一般解決方法（從頭到尾查找一遍）a1a2a3a4…anx…成功和不成功的計算時間都是n二分檢索原理將問題表示為：I=(n,a1,…,an,x)選取一個下標k，可得到三個子問題：I1=(k-1,a1,…,ak-1,x)I2=(1,ak,x)I3=(n-k,ak+1,…,an,x)如果對所求解的問題（或子問題）所選的下標k都是中間元素的下標，k=[(n+1)/2]，則由此產(chǎn)生的算法就是二分檢索算法。二分檢索算法ProcedureBINSRCH(A,n,x,j)integerlow,high,mid,j,n;low1;highnif(n>0)while（low≤high）do{mid[(low+high)/2]

/*取中間值*/

casex<A[mid]:highmid-1/*尋找前一半*/x>A[mid]:lowmid+1/*尋找后一半*/else:jmid;return/*檢索成功*/endcase}j0/*檢索失敗*/EndBINSRCH二分檢索算法實例假設(shè)在數(shù)組A(1:9)中順序放了以下9個元素：-15,-6,0,7,9,23,54,82,101要求檢索的x分別為：101,-14,82X=101Low high mid1 9 56 9 78 9 89 9 9 OKX=-14Low high mid1 9 51 4 21 1 12 1 NO

X=82Low high mid1 9 56 9 78 9 8 OK二分檢索算法正確性的證明用五個特性判斷是否是一個算法根據(jù)算法的描述，滿足五個特性的才是算法證明算法是否正確如果n=0，則不進入循環(huán)，j=0，算法終止否則就會進入循環(huán)與數(shù)組A中的元素進行比較如果x=A[mid]，則j=mid，檢索成功，算法終止否則，若x<A(mid)，則縮小到A(low)和A(mid-1)之間檢索若x>A(mid)，則縮小到A(mid+1)和A(n)之間檢索按上述方式縮小檢索區(qū)總可以在有限步內(nèi)使low>high如果出現(xiàn)這種情況，說明x不在A中，j=0，算法終止二分檢索算法所需的空間和時間所需空間用n個位置存放數(shù)組A，還有l(wèi)ow,high,mid,x,j五個變量需要存儲，共需空間n+5計算時間對于計算時間，需要分別考慮以下幾種情況：成功檢索的最好情況和不成功檢索的最好情況成功檢索的平均情況和不成功檢索的平均情況成功檢索的最壞情況和不成功檢索的最壞情況成功檢索最好情況和不成功檢索最好情況成功的檢索共有n種不成功的檢索共有n+1種A(1)(2)(3)(4)(5)(6)(7)(8)(9)元素-15-6079235482101比較次數(shù)3234132343334433344不成功的檢索成功的檢索二元比較樹572134689內(nèi)結(jié)點,表示一次元素的比較,存放已個mid值外結(jié)點,表示不成功檢索的一種情況每一條路徑表示一個元素的比較序列9-6-1505472382101二分檢索的時間復雜度定理2.2：若n在區(qū)域[2k-1,2k)中，則對于一次成功的檢索，二分檢索至多作k次比較，至少作1次比較；而對于一次不成功的檢索，或者作k-1次比較或者作k次比較。證明考察以n個結(jié)點描述BINSRCH執(zhí)行過程的二元比較樹，所有成功檢索都在內(nèi)部結(jié)點處結(jié)束，而所有不成功檢索都在外部結(jié)點處結(jié)束。由于n在區(qū)域[2k-1,2k)中，因此，所有的內(nèi)部結(jié)點在1，2，…，k級，而所有的外部結(jié)點在k和k+1級（根在1級）。就是說，成功檢索在i級終止所需要的元素比較數(shù)是i，而不成功檢索在i級外部結(jié)點終止的元素比較數(shù)是i-1。二分檢索的時間復雜度最壞情況下的成功檢索計算時間Θ(logn)最壞情況下的不成功檢索計算時間Θ(logn)最好情況下的成功檢索計算時間Θ(1)最好情況下的不成功檢索計算時間Θ(logn)每種不成功的檢索時間都為Θ(logn)成功檢索的平均比較次數(shù)由根到所有內(nèi)部結(jié)點的距離之和稱為內(nèi)部路徑長度I;由根到所有外部結(jié)點的距離之和稱為外部路徑長度E;E=I+2n令S(n)是成功檢索的平均比較次數(shù)。找一個內(nèi)部結(jié)點表示的元素所需的比較次數(shù)是由根到該結(jié)點的路徑長度（即距離）加1。因此，S(n)=I/n+1到一個外部結(jié)點所需要的比較數(shù)是由根到該結(jié)點路徑的長度。因此，U(n)=E/(n+1)由以上各公式可得S(n)=(1+1/n)U(n)-1由于U(n)=(logn)，所以成功檢索的計算時間S(n)也為(logn)二分檢索在各種情況下的檢索時間計算時間最好平均最壞成功的檢索Θ(1)Θ(logn)Θ(logn)不成功的檢索Θ(logn)Θ(logn)Θ(logn)以比較為基礎(chǔ)檢索的時間下界有n個如下關(guān)系的元素:A(1)<A(2)…<A(n),檢索一給定元素X是否在A中出現(xiàn)X:A(1)X:A(2)X:A(n)不成功不成功不成功不成功線性檢索二分檢索X:A([(n+1)/2])X:A([(3n+1)/4])X:A([(n+1)/4])X:A(n)])X:A([(2n+1)/2]+1)X:A([(2n+1)/2]-1)X:A(1)不成功不成功不成功不成功不成功不成功不成功不成功…………以比較為基礎(chǔ)檢索的時間下界定理2.3：設(shè)A(1:n)含有n(n≥1)個不同的元素，排序為A(1)<A(2)<…<A(n)。又設(shè)以比較為基礎(chǔ)去判斷是否x∈A(1:n)的任何算法在最壞情況下所需的最小比較次數(shù)是FIND(n)，那么FIND(n)≥[log(n+1)]

證明若一棵二元樹的所有內(nèi)部結(jié)點所在的級數(shù)小于或等于級數(shù)k，則最多有2k-1個內(nèi)結(jié)點。因此，n≤2k-1,即

FIND(n)=k≥[log(n+1)]。定理表明，任何一種以比較為基礎(chǔ)的算法，其最壞情況時間都不可能低于O(logn)，也就是不可能存在其最壞情況時間比二分檢索數(shù)量級還低的算法。2.3找最大和最小元素問題描述：在含有n個不同元素的集合中同時找出它的最大和最小元素一般解決方法ProcedureSTRAITMAXMIN(A,n,max,min)integeri,n;maxminA(1)fori2tondo{ifA[i]>maxthenmaxA[i]endififA[i]<minthenminA[i]endif}EndSTRAITMAXMINIfA[i]>maxthenmaxA[i]Elseif(A[i]<minthenminA[i]endifendif算法的時間復雜度改進前：2(n-1)改進后：最好n-1，最壞2(n-1)，平均3(n-1)/2可考慮用分治策略來解決這個問題將任一實例I=(n,A(1),…,A(n))分成一些較小的實例來處理。I=(n,A(1),…,A(n))I1=([n/2],A(1),…,A([n/2]))I2=(n-[n/2],A([n/2]+1),…,A(n))……遞歸求取最大和最小元素ProcedureMAXMIN(i,j,fmax,fmin)integeri,j;globaln,A(1:n)case:i=j:fmaxfminA(i):i=j-1:ifA(i)<A(j)thenfmaxA(j);fminA(i)elsefmaxA(i);fminA(j)endif:else:mid[(i+j)/2]

callMAXMIN(i,mid,gmax,gmin)callMAXMIN(mid+1,j,hmax,hmin)

fmaxmax(gmax,hmax)fminmin(gmin,hmin)endcaseEndMAXMIN只有一個或兩個元素時遞歸調(diào)用部分求解答案的部分過程MAXMIN模擬A(1)(2)(3)(4)(5)(6)(7)(8)(9)元素2213-5-815601731471,9,1,3,4,5,3,3,1,2,1,5,6,9,8,9,6,7,①22,13②-5,-5③22,-5④15,-8⑤22,-8⑨60,-8⑧60,17⑥60,17⑦47,31一次遞歸調(diào)用過程MAXMIN的時間復雜度MAXMIN的元素比較次數(shù)T(n)=0 n=11 n=22T([n/2])+2 n>2當n=2k(k是某個正整數(shù))時，有T(n)=3n/2-2T(n)=2T(n/2)+2=4T(n/4)+4+2……=2k-1T

(2)+(2+22+…+2i+…+2k-1)=2k-1+2k-2=3n/2-2當n>2時與直接算法的比較次數(shù)2(n-1)相比，比較次數(shù)減少了25%。MAXMIN算法分析由于遞歸的調(diào)用，MAXMIN所需要的存儲空間較多，遞歸調(diào)用也消耗了部分時間。元素A(i)和A(j)的比較與i和j的比較時間相差不大時，過程MAXMIN不可取。如果設(shè)過程MAXMIN的頻率計數(shù)為C(n)，n=2k，k是一個整數(shù)，并用i>=j-1來代替i=j和i=j-1，有：C(n)2 n=22C(n/2)+3 n>2當n>2時，C(n)=2C(n/2)+3 =4C(n/4)+6+3 …… =2k-1C

(2)+3(1+2+22+…+2i+…+2k-2) =2k+3*2k-1-3 =5n/2-3當n較大時，比較次數(shù)會遠遠大于直接比較算法結(jié)論：如果數(shù)組A的元素間的比較遠比整型變量的比較代價昂貴，則分治法產(chǎn)生效率較高的算法；反之，就得到一個效率較低的程序。2.4歸并分類（排序）問題描述 給定一個含有n個元素(或叫關(guān)鍵字)的集合，把它們按一定的次序分類(如非降次序排序)一般方法(插入法)Forj2tondo將A(j)放到已分類集合A(1:j-1)的正確位置上Repeat插入分類算法描述ProcedureINSERTIONSORT(A,n)A(0)-∞forj2tondoitemA(j);ij-1

whileitem<A(i)doA(i+1)A(i);ii-1repeat

A(i+1)itemrepeatEndINSERTIONSORT數(shù)組元素的移動插入排好序的值可能執(zhí)行0~j次(j=2,3…n)最壞情況的計算時間：2+…+n=(n(n+1)/2)-1=Θ(n2)，最好情況Ω(n)分治策略設(shè)計分類算法I=(n,A(1),…A(n))I1=(n-[n/2],A(1),…A([n/2]))I2=(n-[n/2],A([n/2]+1),…A(n))I=(n,A(1),…A(n))MERGEProcedureMERGESORT(low,high)intergerlow,high

iflow<highthenmid[(low+high)/2]callMERGESORT(low,mid)callMERGESORT(mid+1,high)callMERGE(low,mid,high)endifEndMERGESORT遞歸調(diào)用，分別對分解出來的兩個子問題分類合并兩個已分好類的序列，得到原問題的解分治策略設(shè)計分類算法合并函數(shù)MERGE的實現(xiàn)A(1)A(2)A(3)…A([n/2])A([n/2]+1)…A(n)數(shù)組A已分類序列A已分類序列B輔助數(shù)組B比較大小小值A(chǔ)(1)比較大小小值A(chǔ)([n/2]+1)…………數(shù)組A剩余已分類元素A(1)A([n/2]+1)合并函數(shù)MERGE的實現(xiàn)思想合并函數(shù)MERGE的算法描述ProcedureMERGE(low,mid,high)integerh,i,j,k,low,mid,high;globalA(low:high);localB(low:high)hlow;ilow;jmid+1;whileh≤midandj≤highdoifA(h)≤A(j)thenB(i)A(h);hh+1elseB(i)A(j);jj+1endif

ii+1repeatifh>midthenforkjtohighdoB(i)A(k);ii+1repeatelseforkhtomiddoB(i)A(k);ii+1repeatendifforklowtohighdoA(k)B(k)repeatEndMERGE處理兩個已分類的序列剩余元素的處理過程將已分類的集合復制到A數(shù)組歸并分類算法實例310285179652351423861254450520①②③④285310179652351423861254450520①②③179285310652351423861254450520①②⑤

179285310351652423861254450520①②179285310351652423861254450520①歸并分類算法實例179285310351652423861254450520①179285310351652254423450520861①反復遞歸調(diào)用，合并179254285310351423450520652861合并MERGESORT調(diào)用樹1,106,101,51,34,56,89,108,89,910,105,54,43,31,26,71,12,27,76,6表示一次調(diào)用時的low和high的值只含單個元素的子集合將問題不斷分解成規(guī)模較小的子問題，使之更容易解決。MERGE調(diào)用樹1，1，24，4，56，6，71，2，39，9，106，7，86，8，101，3，51，5，10表示一次MERGE調(diào)用時的low,mid,high值表示A(1:3)和A(4:5)中的元素歸并將處理好的子問題不斷的合并，最終獲得原問題的結(jié)果歸并分類的計算時間T(n)=a n=1,a是常數(shù)2T(n/2)+cn n>1,c是常數(shù)當n=2k時，可得T(n)=2(2T(n/4)+cn/2)+cn=22T(n/4)+2cn=4(2T(n/8)+cn/4)+2cn=23T(n/8)+3cn……=2kT(1)+kcn=an+cnlogn如果2k<n<2k+1，有T(n)≤T(2k+1)，有T(n)=O(nlogn)改進的分類歸并算法procedureMERGESORT1(low,high,p)//利用輔助數(shù)組LINK(low:high)將全程數(shù)組A(low:high)按非降次序分類。LINK中值表示按分類次序給出A下標的表，并把p置于指示這表的開始處//globalA(low:high),LINK(low:high)ifhigh-low+1<16thencallINSERTIONSORT(A,LINK,low,high,p)elsemid<-[(low+high)/2]callMERGESORT1(low,mid,q)callMERGESORT1(mid+1,high,r)callMERGE1(q,r,p)endifendMERGESORT1任何以關(guān)鍵字比較為基礎(chǔ)的分類算法，最壞情況下的時間下界都是Ω(nlogn)，因此，從數(shù)量級的角度上來看，歸并算法是最壞情況下的最優(yōu)算法。下面用二元比較樹給出以比較為基礎(chǔ)的分類算法時間下界的證明。以比較為基礎(chǔ)分類的時間下界關(guān)鍵字分類的二元比較樹1:21:31:32:32:31,2,31,3,23,1,22,1,32,3,13,2,1A(1)<A(2)A(1)>A(2)A(2)<A(3)A(2>A(3)A(1)<A(3)A(1)>A(3)A(2)<A(3)A(2)>A(3)A(1)<A(3)A(1)>A(3)表示一次比較一種可能的分類序列以比較為基礎(chǔ)分類的時間下界由于n個關(guān)鍵字有n!種排列，而每種排列可以是某種特定輸入下的分類結(jié)果，因此比較樹必定至少有n!個外結(jié)點，每個外結(jié)點表示一種可能的分類序列。對于任何一個以比較為基礎(chǔ)的算法，在描述其執(zhí)行的那棵比較樹中，由根到某外結(jié)點的路徑長度表示生成該外結(jié)點中那個分類序列所需要的比較次數(shù)。從而，要求出所有以比較為基礎(chǔ)的對n個關(guān)鍵字分類的算法最壞情況下界，只需求出這些算法對應(yīng)的比較樹的最小高度。據(jù)二元樹的性質(zhì)可知，如果一棵二元樹的所有內(nèi)結(jié)點的級數(shù)均小于或等于k，則該樹至多有2k個外結(jié)點（比內(nèi)結(jié)點數(shù)多1）。

令T(n)=k，則n!<=2T(n)

而當n>1時有n!>=n(n-1)…([n/2])>=(n/2)n/2

因此，對于n>=4有T(n)>=(n/2)log(n/2)>=(n/4)logn。故以比較為基礎(chǔ)的分類算法的最壞情況的時間下界為Ω(nlogn)2.5快速分類（排序）ProcedureQUICKSORT(p,q)integerp,q;globaln,A(1:n)ifp<qthenj=q+1callPARTITION(p,j)callQUICKSORT(p,j-1)callQUICKSORT(j+1,q)endifEndQUICKSORTPARTITION算法ProcedurePARTITION(m,p)Integerm,p,i;globalA(m:p-1);V=A(m);i=m;Looploopi=i+1untilA(i)>=vrepeatloopp=p-1untilA(p)<=vrepeatifi<pthencallINTERCHANGE(A(i),A(p))elseexitRepeatA(m)=A(p);A(p)=vEndPARTITIONPARTITION算法實例(1)(2)(3)(4)(5)(6)(7)(8)(9)(10)ip6545505560

85807570+∞65654575808560555070+∞38654550808560557570+∞47654550558560807570+∞56657075808560555045+∞29

604550556585807570+∞QUICKSORT算法分析假設(shè)參加分類的n個元素各不相同;PARTITION中的劃分元v是隨機選取的.要分析QUICKSORT,只需計算出它的元素比較次數(shù)C(n)即可.令C(n)在最壞情況下的值為CW(n),易知CW(n)=O(n2)令C(n)在平均情況下的值為CA(n),則

CA(n)=n+1+1/nΣi≤k≤n(CA(k-1)+CA(n-k))

CA(n)<2(n+1)loge(n+1)=O(nlogn)QUICKSORT算法分析最壞情況：O(n2)平均情況：O(nlogn)2.6選擇問題2.6.1選擇問題算法(找第K小元素)ProcedureSELECT(A,n,k)integern,k,m,r,j;m=1;r=n+1;A(n+1)=+∞;Loopj=r;callPARTITION(m,j)case:k=j:return:k<j:r=j:else:m=j+1endcaseEndSELECT最壞情況：O(n2)平均情況：O(n)2.6選擇問題（續(xù)）最壞情況時間是O(n)的選擇算法采用二次取中值規(guī)則選取劃分元素二次取中值規(guī)則選取劃分元素例：設(shè)n=35,r=7。分為n/r=5個元素組：B1，B2，B3，B4，B5；每組有7個元素。B1--B5按照各組的mi的非增次序排列。mm為各mi的中間值，1≤i≤5。mm中間值小于等于mm的元素大于等于mm的元素非降次序B1B2B3B4B5按照mi的非降次序排列二次取中值規(guī)則選取劃分元素由于r個元素的中間值是第小元素。則，至少有個mi小于或等于mm；至少有個mi大于或等于mm。則，至少有個元素小于或等于（或大于或等于）mm。

當r=5，則使用兩次取中間值規(guī)則來選擇v=mm，可推出，至少有個元素小于或等于選擇元素v。至多有個元素大于v。至多有0.7n+1.2個元素小于v。

故，這樣的v可近似平均地劃分A中的n個元素。使用二次取中規(guī)則的選擇算法ProcedureSELECT2(A,k,n)1若n<=r，則采用插入法直接對A分類并返回第K小元素。2把A分成大小為r的[n/r]個子集合，忽略剩余的元素。3設(shè)m＝｛m1,m2,…,m[n/r]｝是上面[n/r]個子集合的中間值的集合4v=SELECT2(m,[[n/r]/2],[n/r])5用PARTITION劃分A，v作為劃分元素。6假設(shè)v在位置j。7case:k=j:return(v):k<j:設(shè)S是A(1:j-1)中元素的集合，return(SELECT2(S,k,j-1)):else:設(shè)R是A(j+1,n)中元素的集合，return(SELECT2(R,k-j,n-j))endcaseEndSELECT2SELECT2算法的分析(一)首先考慮r=5且A中各元素互不相同的情況設(shè)總的時間為T(n)Step1:O(1)Step3:每個mi為O(1),故總的為O(n)Step2,5,6:O(n)Step4:T(n/r)(由于r=5,所以T(n/r)=T(n/5))Step7:T(3n/4)當n>=24時由此得：T(n)<=T(n/5)+T(3n/4)+cn用歸納法易證：當n>=1時T(n)<=20cn故：最壞情況時間是O(n)SELECT2算法的分析(二)二次取中值法中，小于或等于v的元素個數(shù)至少為［r/2］[1/2[n/r]]，故大于或等于v的元素至多為n-［r/2］[1/2[n/r]]。（注：[]為上取整）。Step7:r=5時，

[5/2][1/2[n/5]]≥3×1/2×(n/5)=3n/10，則

n-3n/10=7n/10由此，T(n)=T(n/5)+T(7n/10)+O(n)故r=5時，算法在最壞情況下可以用O(n)的時間執(zhí)行完畢。SELECT2算法的分析(二)T(n)=T(n/5)+T(7n/10)+O(n)用替換法:猜測T(n)=O(n)，則T(n)≤dn。T(n)=T(n/5)+T(7n/10)+O(n)

≤d*n/5+d*7n/10+cn

=9/10*dn+cn

≤dn(當d≥10c時成立)故T(n)=O(n)SELECT2算法的分析(續(xù))其次考慮A中元素不是完全不同的情況在這種情況下，當在step5調(diào)用PARTITION時，由于所產(chǎn)生的S和R這兩種集合中可能有一些等于v的元素。處理此問題的一種方法是把A分成三個集合U，S和R，使U由所有與v相同的元素組成，S是A中所有比v小的元素的集合，A中所有比v大的元素組成R。于是將Step7修改成：Case

:|S|>=k:return(SELECT2(S,k,|S|)):|S|+|U|>=k:return(v):else:return(SELECT2(R,k-|S|-|U|,|R|))Endcase修改后的SELECT2的時間復雜度仍是O(n)SELECT2的SPARKS的描述算法procedureSEL(A,m,p,k)//返回一個i，使得i∈[m,p]，且A(i)是A(m:p)中第k小元素，r是一個全程變量，其取值為大于1的整數(shù)globalr;integern,i,jifp-m+1≤rthencallINSERTIONSORT(A,m,p);return(m+k-1);endifloopn←p-m+1//元素數(shù)//fori←1ton/rdo//計算中間值//callINSERTIONSORT(A,m+(i-1)*r,m+i*r-1)//將中間值收集到A(m:p)的前部//callINTERCHANGE(A(m+i-1),A(m+(i-1)r+r/2-1))repeatj←SEL(A,m,m+n/r-1,n/r/2)//mm//callINTERCHANGE(A(m),A(j))//產(chǎn)生劃分元素//j←p+1callPARTITION(m,j)case:j-m+1=k:return(j):j-m+1>k:p←j-1:else:k←k-(j-m+1);m←j+1endcaserepeatendSEL2.7斯特拉森矩陣乘法令A和B為n×n的矩陣，則：由矩陣加定義直接產(chǎn)生的矩陣加算法的時間為O(n2)由矩陣乘定義直接產(chǎn)生的矩陣乘算法的時間為O(n3)用分治法解