[理學(xué)]《算法設(shè)計與分析》第05章課件(PPT 103頁)

1、算法設(shè)計與分析DeSign and Analysis of AlgorithmsIn C+“十一五”國家級規(guī)劃教材 陳慧南 編著電子工業(yè)出版社第1頁，共103頁。第2部分 算法設(shè)計策略第2頁，共103頁。第5章 分治法 第3頁，共103頁。5.1 分治法的基本思想 5.2 求最大最小元 5.3 二分搜索 5.4 排序問題5.5 選擇問題5.6 斯特拉森矩陣乘法 第4頁，共103頁。5.1 一般方法 第5頁，共103頁。5.1.1 分治法的基本思想 分治法顧名思義就是分而治之。一個問題能夠用分治法求解的要素是：第一，問題能夠按照某種方式分解成若干個規(guī)模較小、相互獨立且與原問題類型相同的子問題；第

2、二，子問題足夠小時可以直接求解；第三，能夠?qū)⒆訂栴}的解組合成原問題的解。由于分治法要求分解成同類子問題，并允許不斷分解，使問題規(guī)模逐步減小，最終可用已知的方法求解足夠小的問題，因此，分治法求解很自然導(dǎo)致一個遞歸算法。 第6頁，共103頁。【程序5-1】 分治法SolutionType DandC(ProblemType P)ProblemType P1，P2，Pk;if (Small(P) return S(P);else Divide(P，P1，P2，Pk);Return Combine(DandC(P1)， DandC(P2)，DandC(Pk); 第7頁，共103頁?！境绦?-2】 一分

3、為二的分治法SolutionType DandC(int left，int right)if (Small(left, right) return S(left,right);else int m=Divide(left，right); Return Combine(DandC(left，m)， DandC(m+1，right); 第8頁，共103頁。5.1.2 算法分析 采用分治法求解問題通常得到一個遞歸算法。如果較大的問題被分解成同樣大小的幾部分，那么分析相應(yīng)算法的執(zhí)行時間，往往可得到如下的遞推關(guān)系式：T(n) = aT(n/b) + cnk，T(1) = c 第9頁，共103頁。定理5-

4、1 設(shè)a,b,c和k為常數(shù)，T(n)=aT(n/b)+cnk，T(1)=c，則， 第10頁，共103頁。第11頁，共103頁。設(shè)r= bk /a ，下面分三種情況計算 。（1）若r1，則 所以 第12頁，共103頁。例如：(1) T(n)=2T(n/2)+n a=2,b=2,k=1,a=bk 所以 T(n)= (nlog(n) (2) T(n)=4T(n/4)+n2 a=4,b=4,k=2,abk 所以 T(n)= (n4)第13頁，共103頁。5.1.3 數(shù)據(jù)結(jié)構(gòu) 【程序53】 可排序表類template struct E /可排序表中元素的類型operator K( ) const ret

5、urn key;/重載類型轉(zhuǎn)換運算符K key;/關(guān)鍵字可以比較大小D data;/其他數(shù)據(jù);第14頁，共103頁。 template class SortableList /可排序表類 public:SortableList(int mSize)/構(gòu)造函數(shù) maxSize=mSize;l=new TmaxSize;n=0;SortableList()delete l;/析構(gòu)函數(shù) private: T *l ;/定義動態(tài)一維數(shù)組int maxSize;/線性表的最大表長int n;/線性表的實際長度; 第15頁，共103頁。5.2 求最大最小元 第16頁，共103頁。 問題在一個元素集合中尋找

6、最大元素和最小元素的問題。第17頁，共103頁。5.2.1 分治法求解【程序54】 求最大最小元template void SortableList:MaxMin(T& max, T& min) const if (n=0)return; max=min=l0; for (int i=1; imax) max=li; if(limin) min=li; / /Tn=2(n-1) 第18頁，共103頁。5.2.1 分治法求解【程序54】 求最大最小元template void SortableList:MaxMin(T& max, T& min)const if (n=0)return; max

7、=min=l0; for (int i=1; imax) max=li; else if(limin) min=li; Wn=2(n-1) (遞減有序） Bn=n-1(遞增有序）第19頁，共103頁?！境绦?5】分治法求最大最小元template void SortableList:MaxMin(int i, int j, T& max, T& min) const T min1,max1;if (i=j) max=min=li; else if (i=j-1) if (lilj) max=lj; min=li; else max=li; min=lj; 第20頁，共103頁。 else in

8、t m=(i+j)/2; MaxMin(i,m,max,min); MaxMin(m+1,j,max1,min1); if (maxmin1) min=min1; 第21頁，共103頁。5.2.2 時間分析定理52 設(shè)有n個元素的表，假定n是2的冪，即n=2k，k是正整數(shù)，程序55在最好、平均和最壞情況下的比較次數(shù)都為3n/22。第22頁，共103頁。n=2k,T(n)=2T(n/2)+2T(n)=3n/2-2第23頁，共103頁。5.3 二分搜索第24頁，共103頁。問題在有序表（已按關(guān)鍵字值非減排序）中搜索給定元素的問題。第25頁，共103頁。5.3.1 分治法求解int Sortable

9、List:BSearch(const T& x, int left,int right)const后置條件: 在范圍為left,right的表中搜索與x有相同關(guān)鍵字值的元素；如果存在該元素，則函數(shù)返回該元素在表中的位置，否則函數(shù)返回1，表示搜索失敗。第26頁，共103頁。二分搜索1.二分搜索的基本思想二分搜索的基本思想是：首先將待查值x與有序表l0到ln-1的中的下標(biāo)為mid上的元素進行比較，若相等，則查找成功；否則，若xlmid，則在lmid+1到ln-1中繼續(xù)查找。第27頁，共103頁。每通過一次關(guān)鍵字的比較，搜索區(qū)間的長度就縮小一次，如此不斷進行下去，直到找到值等于x的元素；若當(dāng)前的查找

10、區(qū)間為空,表示查找失敗。從上述查找思想可知，每進行一次關(guān)鍵字比較，都將原區(qū)間一分為二，故稱為二分搜索。如果把要搜索區(qū)間的長度縮小一半，就稱為對半搜索。第28頁，共103頁?！境绦?6】二分搜索算法框架template int SortableList:BSearch(const T& x, int left,int right)const if (left=right) int m=Divide(left+right); if (xlm) return BSearch(x,m+1,right); else return m; return -1; 第29頁，共103頁。5.3.2 對半搜索 對

11、半搜索 對半搜索是一種二分搜索。設(shè)當(dāng)前搜索的子表 為（aleft,aleft+1,aright）， 令 m=(left+right)/2 第30頁，共103頁。例如，假設(shè)給定有序表中關(guān)鍵字為8,17,25,44,68,77,98,100,115,125，將查找K=17和K=120的情況描述為以下形式。第31頁，共103頁。第32頁，共103頁。第33頁，共103頁。第34頁，共103頁?！境绦?7】 對半搜索遞歸算法template int SortableList:BSearch(const T& x, int left, int right)const if (left=right) in

12、t m=(left+right)/2; if (xlm) return BSearch(x,m+1,right); else return m; return -1; 第35頁，共103頁。二分查找的性能分析 為了分析二分查找的性能，可以用二叉樹來描述二分查找過程。把當(dāng)前查找區(qū)間的中點作為根結(jié)點，左子區(qū)間和右子區(qū)間分別作為根的左子樹和右子樹，左子區(qū)間和右子區(qū)間再按類似的方法，由此得到的二叉樹稱為二分查找的判定樹。例如，對關(guān)鍵字序列8,17,25,44,68,77,98,100,115,125，的判定樹下圖。第36頁，共103頁。二分查找的性能分析 查找成功：最好：Ws=1；最壞：Ws= log

13、n +1= O(logn)查找失?。篧f= logn +1 = (logn)第37頁，共103頁。搜索成功的平均時間復(fù)雜度：從上圖可知，查找根結(jié)點68，需一次查找，查找17和100，各需二次查找，查找8、25、77、115各需三次查找，查找44、98、125各需四次查找。于是，可以得到結(jié)論：二叉樹第K層結(jié)點的查找次數(shù)各為k次(根結(jié)點為第1層)，而第k層結(jié)點數(shù)最多為2k-1個。假設(shè)該二叉樹的深度為h， 則二分查找的成功的平均查找次數(shù)為（假設(shè)每個結(jié)點的查找概率相等）：第38頁，共103頁。ASL= = 1/n 1/n(1+22+322+h2h-1) =1/n設(shè)s= =20+221+322+(h-1

14、)2h-2+h2h-1則2s=21+222+(h-2)2h-2+(h-1)2h-1+h2hs=2s-s=h .2h-(20+21+22+2h-2+2h-1) =h .2h-(2h-1) 第39頁，共103頁。ASL=1/n( log2(n+1) (2h-1+1)-n) =1/n( log2(n+1) (n+1)-n) =(n+1)/n log2(n+1)-1 =(1+1/n) log2(n+1)-1當(dāng)n很大時，ASL log2(n+1)-1 可以作為二分查找成功時的平均查找長度，它的時間復(fù)雜度為 (log2n)。 根據(jù)二叉樹的性質(zhì)，最大的結(jié)點數(shù)n=2h-1，h=log2(n+1) ，于是可以得

15、到平均查找次數(shù)ASL=s/nASL= 1/n(h2h-(2h-1)第40頁，共103頁。5.3.4 搜索算法的時間下界 定理56 在一個有n個元素的集合中，通過關(guān)鍵字值之間的比較，搜索指定關(guān)鍵字值的元素，任意這樣的算法在最壞情況下至少需要作log n+1次比較。第41頁，共103頁。5.4 排序問題 第42頁，共103頁。 問題 排序是將一個元素序列調(diào)整為按指定關(guān)鍵字值的遞增（或遞減）次序排列的有序序列。 第43頁，共103頁。合并兩個有序表：合并算法排序也屬于分治方法。合并（Merge）就是將兩個或多個有序表合并成一個有序表，例如下圖所示的兩個有序表經(jīng)合并運算后得到一個有序表。我們在此只用到

16、兩個有序表的合并，稱為二路合并Two-way merge）。5.4.1 合并排序第44頁，共103頁。合并排序（Merge sort）就是利用這種合并過程進行排序，即先將n個數(shù)據(jù)看成n個長度為l的表，將相鄰的表成對合并，得到長度為2的n/2個有序表；進一步再將相鄰表成對合并，得到長度為4的n/4個有序表；如此重復(fù)做下去，直至所有數(shù)據(jù)均合并到一個長度為n的有序表為止，即完成排序。上述每一次的合并過程稱為一趟Pass），整個排序過程叫二路合并排序。下圖是二路合并排序過程的一個例子。合并排序第45頁，共103頁。7 15 13 10 4 20 19 87 15 10 13 4 20 8 197 15

17、 13 10 4 20 19 8 7 10 13 15 4 8 19 20 4 7 8 10 13 15 19 20第46頁，共103頁。合并兩個有序序列第47頁，共103頁?！境绦?9】 合并兩個有序序列（Merge函數(shù)）template void SortableList:Merge(int left, int mid,int right) T* temp=new Tright-left+1; int i=left,j=mid+1,k=0; while ( i=mid )& (j=right) if (li=lj) tempk+=li+; else tempk+=lj+; while (i

18、=mid) tempk+=li+; while (j=right) tempk+=lj+; for (i=0,k=left;k=right;) lk+ = tempi+; 第48頁，共103頁。 分治法求解 將待排序的元素序列一分為二分，得到兩個長度基本相等的子序列，如同對半搜索的做法；然后對兩個子序列分別排序，如果子序列較長，還可繼續(xù)細(xì)分，直到子序列的長度不超過1為止；當(dāng)分解所得的子序列已排列有序，可以采用上面介紹的將兩個有序子序列，合并成一個有序子序列的方法，實現(xiàn)將子問題的解組合成原問題解，這是分治法不可缺少的一步。第49頁，共103頁。 對于二路合并，如果數(shù)據(jù)個數(shù)n是2的整數(shù)次方，則所需

19、的趟數(shù)為logn，例如n=8，logn=3，故共需三趟合并過程。如果n不是2的整數(shù)次方，則在每趟合并時表的數(shù)目不一定總是偶數(shù)個。若表的數(shù)目為奇數(shù)，就剩下一個表要“輪空”，直接進入下一趟。這樣，下一趟合并時此表的長度與其它的表將不相同，因此我們設(shè)計的合并過程，并不要求待合并的兩個表長度必須相同。 第50頁，共103頁?！境绦?10】兩路合并排序template void SortableList:MergeSort(int left,int right) if (leftright) int mid = (left+right)/2; MergeSort(left,mid); MergeSort

20、(mid+1,right); Merge(left,mid,right); template void SortableList:MergeSort() MergeSort(0,n-1);第51頁，共103頁。第52頁，共103頁。 性能分析合并排序遞歸算法的時間復(fù)雜度為 (nlog n)。定理5-1 設(shè)a,b,c和k為常數(shù)，T(n)=aT(n/b)+cnk，T(1)=c，則， 第53頁，共103頁。使用遞歸樹可以形象地看到遞推式的迭代過程。 例2-13 T(n) = 2T(n/2) + n的遞歸樹遞歸路徑：n-(1/2)n-(1/2)2n.(1/2)kn1(1/2)kn=1，即n/2k=1，

21、即2k=n，k=log2n=logn所以 T(n)=n*(logn+1)= (nlogn)第54頁，共103頁。5.4.2 快速排序快速排序采用一種特殊的分劃操作對排序問題進行分解，其分解方法是：在待排序的序列(K0,K1,Kn-1)中選擇一個元素作為分劃元素，也稱為主元（pivot）。不妨假定選擇K為主元。經(jīng)過一趟特殊的分劃處理將原序列中的元素重新排列，使得以主元為軸心，將序列分成左右兩個子序列。主元左測子序列中所有元素都不大于主元，主元右測子序列中所有元素都不小于主元。15 7 13 10 4 20 19 8 8 7 13 10 4 15 19 20第55頁，共103頁。1、主元最后的位置

22、就是它最終的合適位置，進一步的運算過程中此數(shù)據(jù)即不必再動；2、以后的排序運算只需在劃分成的兩部分里進行，兩部分之間不會再有數(shù)據(jù)互換。3、第一次劃分以后，再用相同的算法對劃成的部分進行類似的運算，即從每部分中任選一個數(shù)據(jù)將其劃分成更小的兩部分，依此遞歸地做下去，直至每個小部分中的數(shù)據(jù)個數(shù)均不超過一個為止，排序過程即結(jié)束。15 7 13 10 4 20 19 8 8 7 13 10 4 15 19 20第56頁，共103頁。 分劃操作第57頁，共103頁?！境绦?11】 分劃函數(shù)template int SortableList:Partition(int left, int right) /前置

23、條件：leftright int i=left,j=right+1; do do i+; while (lilleft); if (ij) Swap(i,j); while (ij); Swap(left,j); return j; 第58頁，共103頁?？焖倥判蛩惴ǖ?9頁，共103頁。【程序512】快速排序 template void SortableList:QuickSort() QuickSort(0,n-1);template void SortableList:QuickSort(int left,int right) if(leftright) int j=Partition(

24、left,right); QuickSort(left,j-1); QuickSort(j+1,right); 第60頁，共103頁。若快速排序出現(xiàn)最壞的情形（每次能劃分成兩個子區(qū)間，但其中一個是空），因此，快速排序的最壞時間復(fù)雜度為O(n2)?？焖倥判蛩加玫妮o助空間為棧的深度，故最好的空間復(fù)雜度為O（logn），最壞的空間復(fù)雜度為O(n2)。若快速排序出現(xiàn)最好的情形（左、右子區(qū)間的長度大致相等），快速排序的最好時間復(fù)雜度應(yīng)為O（nlog2n）。 時間分析理論上已經(jīng)證明，快速排序的平均時間復(fù)雜度也為O（nlogn）。第61頁，共103頁。平均情況時間 第62頁，共103頁。第63頁，共103

25、頁。5.4.3 排序算法的時間下界定理 57 任何一個通過關(guān)鍵字值比較對n個元素進行排序的算法，在最壞情況下，至少需作（n/4）log n次比較。第64頁，共103頁。第65頁，共103頁。5.5 選擇問題 第66頁，共103頁。問題選擇問題（select problem）是指在n個元素的集合中，選出某個元素值大小在集合中處于第k位的元素，即所謂的求第k小元素問題(kth-smallest)。 第67頁，共103頁。5.5.1 分治法求解 設(shè)原表長度為n，假定經(jīng)過一趟分劃，分成兩個左右子表，其中左子表是主元及其左邊元素的子表，設(shè)其長度為p，右子表是主元右邊元素的子表。那么，若k=p，則主元就是

26、第k小元素；否則若kp，則第k小元素必定在右子表中，需求解的子問題成為在右子表中求第k-p小元素。15 7 13 10 4 20 19 8 8 7 13 10 4 15 19 20第68頁，共103頁。5.5.2 隨機選擇主元 隨機選主元算法 假定表中元素各不相同，并且隨機選擇主元，即在下標(biāo)區(qū)間left,right中隨機選擇一個下標(biāo)r，以該下標(biāo)處的元素為主元。 第69頁，共103頁。 【程序513】Select函數(shù)template ResultCode SortableList:Select1(T& x,int k) if(nn|k=0) return OutOfBounds; int lef

27、t=0, right=n; ln = INFTY; do int j=rand()% (right-left+1)+left; Swap(left,j); j=Partition(left, right); if (k=j+1) x=lj;return Success; else if (kj+1) right=j; else left=j+1; while (true); 第70頁，共103頁。定理58 程序513的Select算法的平均時間A(n)=O(n)。算法的最壞情況時間復(fù)雜度O(n2) 。第71頁，共103頁。5.5.3 線性時間選擇算法改進的選擇算法采用二次取中法(median

28、of medians rule)確定主元 第72頁，共103頁。第73頁，共103頁。 【程序514】 線性時間選擇算法ResultCode SortableList:Select(T& x,int k) if(nn|k=0) return OutOfBounds;int j=Select(k,0,n-1,5);x=lj;return Success; 第74頁，共103頁。template int SortableList:Select(int k, int left,int right,int r) int n=right-left+1; if (n=r) InsertSort(left,

29、right); return left+k-1; 第75頁，共103頁。 for (int i=1;i=n/r;i+) InsertSort(left+(i-1)*r,left+i*r-1); Swap(left+i-1, left+(i-1)*r+Ceil(r,2)-1); int j=Select(Ceil(n/r,2),left,left+(n/r)-1,r ); Swap(left,j); j =Partition(left,right); if (k=j-left+1) return j; else if (kj-left+1) return Select(k,left,j-1,r)

30、; else return Select(k-(j-left+1),j+1,right,r); 第76頁，共103頁。5.5.4 時間分析 以二次取中的中間值mm為主元，經(jīng)過一趟分劃，左、右兩個子表的大小均至多為： nn/r/2 r/2 設(shè)T(n)為當(dāng)表長為n時執(zhí)行程序514所需的時間。T(n)由三部分時間組成： T(n)T(n/5)+T(3n/4)+cn 用歸納法容易證明，T(n)20cn，n1是線性時間的。 第77頁，共103頁。5.5.5 允許重復(fù)元素的選擇算法由于允許包含相同元素，左子表中除了小于mm的元素外，還包含與mm相同值的元素。因此，左子表的大小至多可達 nn/r/2 r/2+

31、1/2 n/r/2 r/2 = n-1/2 n/r/2 r/2 容易用歸納法證明對于所有n90， T(n)T(n/9)+T(7n/8)+cn72cn，n90 第78頁，共103頁。5.6 斯特拉森矩陣乘法 第79頁，共103頁。問題 矩陣相乘 第80頁，共103頁。矩陣乘積的Strassen算法 C=AB=(cij)nn。 求C=AB即對n2個元素cij進行計算，故要作n3次乘法。相當(dāng)時間內(nèi)沒有人懷疑過是否可以用少于n3次乘法來完成。其實不然，先以n=2的矩陣乘積為例。 對于矩陣第81頁，共103頁。則有：共需作8次乘法和4次加法。第82頁，共103頁。分治法求解大矩陣 C11A11B11+A

32、12B21C12A11B12+A12B22 C21A21B11+A22B21 C22A21B12+A22B22一個四階方陣可以看作由4個二階方陣組成第83頁，共103頁。分治法求解大矩陣 C11A11B11+A12B21C12A11B12+A12B22 C21A21B11+A22B21 C22A21B12+A22B22一個n階方陣可以看作由4個n/2階的方陣組成，二個n階方陣的乘積，轉(zhuǎn)化為八個n/2階方陣的乘積和4個n/2階方陣的加法。T(n)=(n3) 第84頁，共103頁。定理5-1 設(shè)a,b,c和k為常數(shù)，T(n)=aT(n/b)+cnk，T(1)=c，則， 第85頁，共103頁。5.6

33、.2 斯特拉森分治法P=(A11+A22)(B11+B22)Q=(A21+A22)B11R=A11(B12-B22)S=A21(B21-B11)T=(A11+A12)B22U=(A21-A11)(B11+B12)V=(A12-A22)(B21+B22)第86頁，共103頁。C11=P+S-T+VC12=R+TC21=Q+SC22=P+R-Q+UT(n)= (nlog 7)(n2. 81) 第87頁，共103頁。2*2矩陣的最少乘法次數(shù)是7。目前最好的矩陣乘法的時間上界是：O(n2.376)。第88頁，共103頁。我們研究兩個n位二進制數(shù)相乘的問題。用普通的方法運算，將乘數(shù)的每一位（由低位至高位）逐個去乘被乘數(shù)，每乘一次將乘積與原來的積相加，然后乘數(shù)和乘積移位一步，如此下去直至乘數(shù)的最高位運算完即得出結(jié)果，這樣運算共需n2 次一位乘一位運算，n(n-1)次一位加一位運算和n次移位，假設(shè)兩個一位數(shù)相乘，兩個一位數(shù)相加和任何數(shù)移位一步所需運算