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

2022/11/23第2部分算法設(shè)計(jì)策略第5章分治法

2022/11/22第2部分算法設(shè)計(jì)策略第5章分治法2022/11/235.2

求最大最小元5.1

分治法的基本思想5.3

二分搜索5.4

排序問(wèn)題5.5選擇問(wèn)題5.6斯特拉森矩陣乘法

2022/11/225.2求最大最小元2022/11/235.2求最大最小元

2022/11/225.2求最大最小元2022/11/23

問(wèn)題在一個(gè)元素集合L中尋找最大元素和最小元素的問(wèn)題。一般方法？2022/11/22問(wèn)題2022/11/235.2.1

分治法求解【程序5－4】求最大最小元template<classT>voidSortableList<T>::MaxMin(T&max,T&min)const{ if(n==0)return; max=min=l[0]; for(inti=1;i<n;i++){ if(l[i]>max)max=l[i]; if(l[i]<min)min=l[i]; }}時(shí)間復(fù)雜度？2022/11/225.2.1

分治法求解【程序5－4】2022/11/23【程序5－5】分治法求最大最小元template<classT>voidSortableList<T>::MaxMin(inti,intj,T&max,T&min)const{ Tmin1,max1; if(i==j)max=min=l[i];elseif(i==j-1)//只有兩個(gè)元素時(shí)

if(l[i]<l[j]){ max=l[j];min=l[i]; } else{ max=l[i];min=l[j]; } 2022/11/22【程序5－5】分治法求最大最小元2022/11/23 else{ intm=(i+j)/2; MaxMin(i,m,max,min); MaxMin(m+1,j,max1,min1); if(max<max1)max=max1; if(min>min1)min=min1; }}

2022/11/22 else{2022/11/235.2.2時(shí)間分析定理5－2

設(shè)有n個(gè)元素的表，假定n是2的冪，即n=2k，k是正整數(shù)，程序5－5在最好、平均和最壞情況下的比較次數(shù)都為3n/2–2。設(shè)n=2k，易解2022/11/225.2.2時(shí)間分析定理5－2設(shè)n=2022/11/235.1一般方法

2022/11/225.1一般方法2022/11/235.1.1分治法的基本思想

分治法顧名思義就是分而治之。一個(gè)問(wèn)題能夠用分治法求解的要素是：第一，問(wèn)題能夠按照某種方式分解成若干個(gè)規(guī)模較小、相互獨(dú)立且與原問(wèn)題類型相同的子問(wèn)題；第二，子問(wèn)題足夠小時(shí)可以直接求解；第三，能夠?qū)⒆訂?wèn)題的解組合成原問(wèn)題的解。由于分治法要求分解成同類子問(wèn)題，并允許不斷分解，使問(wèn)題規(guī)模逐步減小，最終可用已知的方法求解足夠小的問(wèn)題，因此，分治法求解很自然導(dǎo)致一個(gè)遞歸算法。2022/11/225.1.1分治法的基本思想分治法顧2022/11/23【程序5-1】

分治法SolutionTypeDandC(ProblemTypeP){ ProblemTypeP1，P2，，Pk; if(Small(P))returnS(P); else{ Divide(P，P1，P2，，Pk); ReturnCombine(DandC(P1)，

DandC(P2)，…，DandC(Pk)); }}2022/11/22【程序5-1】分治法2022/11/23【程序5-2】

一分為二的分治法SolutionTypeDandC(intleft，intright){ if(Small(left,right))returnS(left,right); else{ intm=Divide(left，right); ReturnCombine(DandC(left，m)，

DandC(m+1，right)); }}2022/11/22【程序5-2】一分為二的分治法2022/11/235.1.2算法分析

采用分治法求解問(wèn)題通常得到一個(gè)遞歸算法。如果較大的問(wèn)題被分解成同樣大小的幾部分，那么分析相應(yīng)算法的執(zhí)行時(shí)間，往往可得到如下的遞推關(guān)系式：T(n)=aT(n/b)+cnk，T(1)=c

2022/11/225.1.2算法分析采用分治法求解2022/11/23定理5-1設(shè)a,b,c和k為常數(shù)，T(n)=aT(n/b)+cnk，T(1)=c，則，

2022/11/22定理5-1設(shè)a,b,c和k為常數(shù)，2022/11/23n=bm2022/11/22n=bm2022/11/23設(shè)r=bk/a，下面分三種情況計(jì)算。（1）若r<1，則

所以（2）若r=1，則

所以（3）若r>1，則

所以2022/11/22設(shè)r=bk/a，下面分三種情況計(jì)算2022/11/235.1.3

排序問(wèn)題數(shù)據(jù)結(jié)構(gòu)【程序5－3】可排序表類template<classK,classD>structE{//可排序表中元素的類型

operatorK()const{returnkey;}Kkey;Ddata;};2022/11/225.1.3

排序問(wèn)題數(shù)據(jù)結(jié)構(gòu)【2022/11/23template<classT>classSortableList{//可排序表類public:SortableList(intmSize);~SortableList();

private:

T*l;//指向動(dòng)態(tài)生成的一位數(shù)組

intmaxSize;intn;};2022/11/22template<classT>2022/11/235.3二分搜索2022/11/225.3二分搜索問(wèn)題在有序表（已按關(guān)鍵字值非減排序）中搜索給定元素的問(wèn)題。a0a0am-1amam+1an-2an-1……2022/11/23問(wèn)題a0a0am-1amam+1an-2an-1……20222022/11/235.3.1

分治法求解intSortableList<T>::BSearch(constT&x,intleft,intright)const說(shuō)明:

在范圍為[left,right]的表中搜索與x有相同關(guān)鍵字值的元素；如果存在該元素，則函數(shù)返回該元素在表中的位置，否則函數(shù)返回－1，表示搜索失敗。2022/11/225.3.1

分治法求解intSort2022/11/23【程序5－6】二分搜索算法框架template<classT>intSortableList<T>::BSearch(constT&x,intleft,intright)const{ if(left<=right){intm=Divide(left+right);if(x<l[m])returnBSearch(x,left,m-1); elseif(x>l[m])

returnBSearch(x,m+1,right); elsereturnm;}return-1;}2022/11/22【程序5－6】二分搜索算法框架2022/11/235.3.2

對(duì)半搜索

對(duì)半搜索對(duì)半搜索是一種二分搜索。設(shè)當(dāng)前搜索的子表為（aleft,aleft+1,…,aright），令

m=(left+right)/2

2022/11/225.3.2

對(duì)半搜索對(duì)半搜索2022/11/23【程序5－7】對(duì)半搜索遞歸算法template<classT>intSortableList<T>::BSearch(constT&x,intleft,intright)const{if(left<=right){

intm=(left+right)/2;if(x<l[m])returnBSearch(x,left,m-1); elseif(x>l[m])returnBSearch(x,m+1,right);elsereturnm;}return-1;}2022/11/22【程序5－7】對(duì)半搜索遞歸算法2022/11/23定理5－3對(duì)于n0，程序5－7的對(duì)半搜索遞歸函數(shù)BSearch是正確的。程序5-7是尾遞歸函數(shù)，易改為迭代形式參考程序5-82022/11/22定理5－32022/11/23//程序5-8：對(duì)半搜索的迭代算法template<classT>intSortableList<T>::BSearch1(constT&x)const{ intm,left=0,right=n-1; while(left<=right){ m=(left+right)/2; if(x<l[m])right=m-1; elseif(x>l[m])left=m+1; elsereturnm; //搜索成功

} return-1; //搜索失敗}2022/11/22//程序5-8：對(duì)半搜索的迭代算法2022/11/235.3.3

二叉判定樹(shù)

二分搜索過(guò)程的算法行為可以用一棵二叉樹(shù)來(lái)描述。通常稱這棵描述搜索算法執(zhí)行過(guò)程的二叉樹(shù)為二叉判定樹(shù)(binarydecisiontree)。2022/11/225.3.3

二叉判定樹(shù)二分搜索過(guò)程2022/11/23如何構(gòu)建二叉判定樹(shù)內(nèi)節(jié)點(diǎn)外節(jié)點(diǎn)2022/11/22如何構(gòu)建二叉判定樹(shù)內(nèi)節(jié)點(diǎn)外節(jié)點(diǎn)2022/11/23性質(zhì)5－1

具有n個(gè)內(nèi)結(jié)點(diǎn)的對(duì)半搜索二叉判定樹(shù)的左子樹(shù)上有(n-1)/2個(gè)內(nèi)結(jié)點(diǎn)，右子樹(shù)上有n/2個(gè)內(nèi)結(jié)點(diǎn)。

性質(zhì)5－2

具有n(n>0）個(gè)內(nèi)結(jié)點(diǎn)的二叉判定樹(shù)的高度為logn+1

（不計(jì)外結(jié)點(diǎn)）。

2022/11/22性質(zhì)5－12022/11/23性質(zhì)5－3

若n=2h-1，則對(duì)半搜索二叉判定樹(shù)是滿二叉樹(shù)。

性質(zhì)5－4

若n=2h-1，則對(duì)半搜索二叉判定樹(shù)的外結(jié)點(diǎn)均在h+1層上，否則，在第h或h+1層上，h=logn+1。

2022/11/22性質(zhì)5－32022/11/23定理5－4

對(duì)半搜索算法在成功搜索的情況下，關(guān)鍵字值之間的比較次數(shù)不超過(guò)logn+1。對(duì)于不成功的搜索，算法需要作logn或logn+1次比較。定理5－5

對(duì)半搜索算法在搜索成功時(shí)的平均時(shí)間復(fù)雜度為(logn)。

對(duì)半搜索是一個(gè)最優(yōu)算法2022/11/22定理5－4對(duì)半搜索是一個(gè)最優(yōu)算法2022/11/235.3.4搜索算法的時(shí)間下界

定理5－6

在一個(gè)有n個(gè)元素的集合中，通過(guò)關(guān)鍵字值之間的比較，搜索指定關(guān)鍵字值的元素，任意這樣的算法在最壞情況下至少需要作log

n+1次比較。2022/11/225.3.4搜索算法的時(shí)間下界定理5－2022/11/23練習(xí)1編寫程序?qū)崿F(xiàn)三分搜索算法，分析其時(shí)間復(fù)雜度，并與對(duì)半搜索算法的時(shí)間性能進(jìn)行比較。2022/11/22練習(xí)1編寫程序?qū)崿F(xiàn)三分搜索算法，分析其時(shí)2022/11/235.4排序問(wèn)題

2022/11/225.4排序問(wèn)題2022/11/23

問(wèn)題排序是將一個(gè)元素序列調(diào)整為按指定關(guān)鍵字值的遞增（或遞減）次序排列的有序序列。2022/11/22問(wèn)題2022/11/235.4.1

合并排序

合并兩個(gè)有序序列

兩路合并排序的基本運(yùn)算是把兩個(gè)有序序列合并成一個(gè)有序序列。

2022/11/225.4.1

合并排序合并兩個(gè)有序序2022/11/23【程序5－9】Merge函數(shù)template<classT>voidSortableList<T>::Merge(intleft,intmid,intright){ T*temp=newT[right-left+1];inti=left,j=mid+1,k=0;while((i<=mid)&&(j<=right)) if(l[i]<=l[j])temp[k++]=l[i++];elsetemp[k++]=l[j++];while(i<=mid)temp[k++]=l[i++];while(j<=right)temp[k++]=l[j++]; for(i=0,k=left;k<=right;)l[k++]=temp[i++];}時(shí)間復(fù)雜度分析？2022/11/22【程序5－9】Merge函數(shù)時(shí)間復(fù)雜度2022/11/232022/11/222022/11/23

分治法求解將待排序的元素序列一分為二分，得到兩個(gè)長(zhǎng)度基本相等的子序列；然后對(duì)兩個(gè)子序列分別排序，如果子序列較長(zhǎng)，還可繼續(xù)細(xì)分，直到子序列的長(zhǎng)度不超過(guò)1為止；當(dāng)分解所得的子序列已排列有序，可以將兩個(gè)有序子序列，合并成一個(gè)有序子序列---合并排序2022/11/22分治法求解---合并排序2022/11/23【程序5－10】?jī)陕泛喜⑴判騮emplate<classT>voidSortableList<T>::MergeSort(intleft,intright){if(left<right){intmid=(left+right)/2;MergeSort(left,mid);MergeSort(mid+1,right);Merge(left,mid,right);}}2022/11/22【程序5－10】?jī)陕泛喜⑴判?022/11/23template<classT>voidSortableList<T>::MergeSort(){ MergeSort(0,n-1);}2022/11/22template<classT>2022/11/232022/11/222022/11/23

性能分析合并排序遞歸算法的時(shí)間復(fù)雜度為O(nlog

n)。2022/11/22性能分析2022/11/235.4.2

快速排序快速排序采用一種特殊的分劃操作對(duì)排序問(wèn)題進(jìn)行分解，其分解方法是：在待排序的序列(K0,K1,…,Kn-1)中選擇一個(gè)元素作為分劃元素，也稱為主元（pivot）。不妨假定選擇K為主元。經(jīng)過(guò)一趟特殊的分劃處理將原序列中的元素重新排列，使得以主元為軸心，將序列分成左右兩個(gè)子序列。主元左測(cè)子序列中所有元素都不大于主元，主元右測(cè)子序列中所有元素都大于主元。2022/11/225.4.2

快速排序快速排序采用一種2022/11/23

分劃操作2022/11/22分劃操作2022/11/23【程序5－11】

分劃函數(shù)template<classT>intSortableList<T>::Partition(intleft,intright){//前置條件：leftright inti=left,j=right+1;//初始主元放在最左邊do{doi++;while(l[i]<=l[left]);doj--;while(l[j]>l[left]);if(i<j)Swap(i,j);//交換

}while(i<j); Swap(left,j); //主元作為分界線 returnj;//返回主元位置}2022/11/22【程序5－11】分劃函數(shù)2022/11/23快速排序算法2022/11/22快速排序算法2022/11/23【程序5－12】快速排序template<classT>voidSortableList<T>::QuickSort(){QuickSort(0,n-1);}template<classT>voidSortableList<T>::QuickSort(intleft,intright){ if(left<right){intj=Partition(left,right);QuickSort(left,j-1); QuickSort(j+1,right); }}2022/11/22【程序5－12】快速排序2022/11/23

時(shí)間分析存在的最壞情況存在的最好情況最壞情況時(shí)間

W(n)W(n-1)+n+1

W(n-2)+(n+1)+n

W(1)+(n+1)++3=O(n2)

2022/11/22時(shí)間分析2022/11/23平均情況時(shí)間

2022/11/22平均情況時(shí)間2022/11/232022/11/222022/11/235.4.3排序算法的時(shí)間下界定理5－7

任何一個(gè)通過(guò)關(guān)鍵字值比較對(duì)n個(gè)元素進(jìn)行排序的算法，在最壞情況下，至少需作（n/4）log

n次比較。2022/11/225.4.3排序算法的時(shí)間下界定理5合并排序與快速排序比較1.基本思想2.劃分與組合方法的區(qū)別3.時(shí)間復(fù)雜度2022/11/23合并排序與快速排序比較1.基本思想2022/11/222022/11/235.5選擇問(wèn)題

2022/11/225.5選擇問(wèn)題2022/11/23問(wèn)題選擇問(wèn)題（selectproblem）是指在n個(gè)元素的集合中，選出某個(gè)元素值大小在集合中處于第k位的元素，即所謂的求第k小元素問(wèn)題(kth-smallest)。

2022/11/22問(wèn)題2022/11/235.5.1

分治法求解

設(shè)原表長(zhǎng)度為n，假定經(jīng)過(guò)一趟分劃，分成兩個(gè)左右子表，其中左子表是主元及其左邊元素的子表，設(shè)其長(zhǎng)度為p，右子表是主元右邊元素的子表。那么，若k=p，則主元就是第k小元素；否則若k<p，第k小元素必定在左子表中，需求解的子問(wèn)題成為在左子表中求第k小元素；若k>p，則第k小元素必定在右子表中，需求解的子問(wèn)題成為在右子表中求第k-p小元素。2022/11/225.5.1

分治法求解設(shè)原表長(zhǎng)度為n2022/11/235.5.2

隨機(jī)選擇主元

隨機(jī)選主元算法

假定表中元素各不相同，并且隨機(jī)選擇主元，即在下標(biāo)區(qū)間[left,right]中隨機(jī)選擇一個(gè)下標(biāo)r，以該下標(biāo)處的元素為主元。2022/11/225.5.2

隨機(jī)選擇主元隨機(jī)選主元算2022/11/23

【程序5－13】Select函數(shù)，元素集合為ltemplate<classT>ResultCodeSortableList<T>::Select1(T&x,intk){ //在l中找到第k大元素，通過(guò)x返回if(n<=0||k>n||k<=0)returnOutOfBounds;intleft=0,right=n;l[n]=INFTY;do{

intj=rand()%(right-left+1)+left;

//確定主元

Swap(left,j);

j=Partition(left,right);//劃分

if(k==j+1){x=l[j];returnSuccess;} elseif(k<j+1)right=j; elseleft=j+1; }while(true);}2022/11/22【程序5－13】Select函數(shù)，2022/11/23定理5－8

程序5－13的Select算法的平均時(shí)間A(n)=O(n)。算法的最壞情況時(shí)間復(fù)雜度O(n2)，？。2022/11/22定理5－82022/11/235.5.3

線性時(shí)間選擇算法改進(jìn)的選擇算法采用二次取中法(medianofmediansrule)確定主元

2022/11/225.5.3

線性時(shí)間選擇算法改進(jìn)的選擇2022/11/232022/11/222022/11/23

【程序5－14】線性時(shí)間選擇算法ResultCodeSortableList<T>::Select(T&x,intk){ if(n<=0||k>n||k<=0)returnOutOfBounds; intj=Select(k,0,n-1,5); x=l[j];returnSuccess;}

2022/11/22【程序5－14】線性時(shí)間選擇算法2022/11/23template<classT>intSortableList<T>::Select(intk,intleft,intright,intr){//對(duì)[left…right]范圍內(nèi)的元素分組，每組r個(gè)元素采用二次取中法，確定主元intn=right-left+1;if(n<=r){InsertSort(left,right);//直接排序

returnleft+k-1;

}2022/11/22template<classT>2022/11/23for(inti=1;i<=n/r;i++){InsertSort(left+(i-1)*r,left+i*r-1);

//對(duì)每組元素直接排序

Swap(left+i-1,left+(i-1)*r+Ceil(r,2)-1);}intj=Select(Ceil(n/r,2),left,left+(n/r)-1,r);//定主元

Swap(left,j);j=Partition(left,right);//劃分

if(k==j-left+1)returnj;elseif(k<j-left+1)returnSelect(k,left,j-1,r);elsereturnSelect(k-(j-left+1),j+1,right,r);}2022/11/22for(inti=1;i<=2022/11/235.5.4時(shí)間分析

以二次取中的中間值mm為主元，經(jīng)過(guò)一趟分劃，左、右兩個(gè)子表的大小均至多為：

nn/r/2

r/2

設(shè)T(n)為當(dāng)表長(zhǎng)為n時(shí)執(zhí)行程序5－14所需的時(shí)間。T(n)由三部分時(shí)間組成：

T(n)T(n/5)+T(3n/4)+cn

用歸納法容易證明，T(n)20cn，n1是線性時(shí)間的。

2022/11/225.5.4時(shí)間分析以二次取中的中間值2022/11/235.5.5允許重復(fù)元素的選擇算法由于允許包含相同元素，左子表中除了小于mm的元素外，還包含與mm相同值的元素。因此，左子表的大小至多可達(dá)

nn/r/2

r/2+1/2n/r/2

r/2

=n-1/2n/r/2

r/2

容易用歸納法證明對(duì)于所有n90，

T(n)T(n/9)+T(7n/8)+cn72cn，n902022/11/225.5.5允許重復(fù)元素的選擇算法由于2022/11/235.6斯特拉森矩陣乘法

2022/11/225.6斯特拉森矩陣乘法2022/11/23問(wèn)題矩陣相乘C=AxB2022/11/22問(wèn)題2022/11/235.6.1分治法求解

C11＝A11B11+A12B21C12＝A11B12+A12B22C21＝A21B11+A22B21C22＝A21B12+A22B22T(n)=(n3)2022/11/225.6.1分治法求解C11＝A11B2022/11/235.6.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)2022/11/225.6.2

斯特拉森分治法P=(A112022/11/23C11=P+S-T+VC12=R+TC21=Q+SC22=P+R-Q+UT(n)=(nlog7)(n2.81)

2022/11/22C11=P+S-T+VT(n)=(n2022/11/23練習(xí)2設(shè)計(jì)算法解決大數(shù)相乘問(wèn)題（長(zhǎng)為n位的兩個(gè)2進(jìn)制數(shù)相乘）使其算法復(fù)雜度低于n2。2022/11/22練習(xí)2設(shè)計(jì)算法解決大數(shù)相乘問(wèn)題（長(zhǎng)為n位2022/11/23第2部分算法設(shè)計(jì)策略第5章分治法

2022/11/22第2部分算法設(shè)計(jì)策略第5章分治法2022/11/235.2

求最大最小元5.1

分治法的基本思想5.3

二分搜索5.4

排序問(wèn)題5.5選擇問(wèn)題5.6斯特拉森矩陣乘法

2022/11/225.2求最大最小元2022/11/235.2求最大最小元

2022/11/225.2求最大最小元2022/11/23

問(wèn)題在一個(gè)元素集合L中尋找最大元素和最小元素的問(wèn)題。一般方法？2022/11/22問(wèn)題2022/11/235.2.1

分治法求解【程序5－4】求最大最小元template<classT>voidSortableList<T>::MaxMin(T&max,T&min)const{ if(n==0)return; max=min=l[0]; for(inti=1;i<n;i++){ if(l[i]>max)max=l[i]; if(l[i]<min)min=l[i]; }}時(shí)間復(fù)雜度？2022/11/225.2.1

分治法求解【程序5－4】2022/11/23【程序5－5】分治法求最大最小元template<classT>voidSortableList<T>::MaxMin(inti,intj,T&max,T&min)const{ Tmin1,max1; if(i==j)max=min=l[i];elseif(i==j-1)//只有兩個(gè)元素時(shí)

if(l[i]<l[j]){ max=l[j];min=l[i]; } else{ max=l[i];min=l[j]; } 2022/11/22【程序5－5】分治法求最大最小元2022/11/23 else{ intm=(i+j)/2; MaxMin(i,m,max,min); MaxMin(m+1,j,max1,min1); if(max<max1)max=max1; if(min>min1)min=min1; }}

2022/11/22 else{2022/11/235.2.2時(shí)間分析定理5－2

設(shè)有n個(gè)元素的表，假定n是2的冪，即n=2k，k是正整數(shù)，程序5－5在最好、平均和最壞情況下的比較次數(shù)都為3n/2–2。設(shè)n=2k，易解2022/11/225.2.2時(shí)間分析定理5－2設(shè)n=2022/11/235.1一般方法

2022/11/225.1一般方法2022/11/235.1.1分治法的基本思想

分治法顧名思義就是分而治之。一個(gè)問(wèn)題能夠用分治法求解的要素是：第一，問(wèn)題能夠按照某種方式分解成若干個(gè)規(guī)模較小、相互獨(dú)立且與原問(wèn)題類型相同的子問(wèn)題；第二，子問(wèn)題足夠小時(shí)可以直接求解；第三，能夠?qū)⒆訂?wèn)題的解組合成原問(wèn)題的解。由于分治法要求分解成同類子問(wèn)題，并允許不斷分解，使問(wèn)題規(guī)模逐步減小，最終可用已知的方法求解足夠小的問(wèn)題，因此，分治法求解很自然導(dǎo)致一個(gè)遞歸算法。2022/11/225.1.1分治法的基本思想分治法顧2022/11/23【程序5-1】

分治法SolutionTypeDandC(ProblemTypeP){ ProblemTypeP1，P2，，Pk; if(Small(P))returnS(P); else{ Divide(P，P1，P2，，Pk); ReturnCombine(DandC(P1)，

DandC(P2)，…，DandC(Pk)); }}2022/11/22【程序5-1】分治法2022/11/23【程序5-2】

一分為二的分治法SolutionTypeDandC(intleft，intright){ if(Small(left,right))returnS(left,right); else{ intm=Divide(left，right); ReturnCombine(DandC(left，m)，

DandC(m+1，right)); }}2022/11/22【程序5-2】一分為二的分治法2022/11/235.1.2算法分析

采用分治法求解問(wèn)題通常得到一個(gè)遞歸算法。如果較大的問(wèn)題被分解成同樣大小的幾部分，那么分析相應(yīng)算法的執(zhí)行時(shí)間，往往可得到如下的遞推關(guān)系式：T(n)=aT(n/b)+cnk，T(1)=c

2022/11/225.1.2算法分析采用分治法求解2022/11/23定理5-1設(shè)a,b,c和k為常數(shù)，T(n)=aT(n/b)+cnk，T(1)=c，則，

2022/11/22定理5-1設(shè)a,b,c和k為常數(shù)，2022/11/23n=bm2022/11/22n=bm2022/11/23設(shè)r=bk/a，下面分三種情況計(jì)算。（1）若r<1，則

所以（2）若r=1，則

所以（3）若r>1，則

所以2022/11/22設(shè)r=bk/a，下面分三種情況計(jì)算2022/11/235.1.3

排序問(wèn)題數(shù)據(jù)結(jié)構(gòu)【程序5－3】可排序表類template<classK,classD>structE{//可排序表中元素的類型

operatorK()const{returnkey;}Kkey;Ddata;};2022/11/225.1.3

排序問(wèn)題數(shù)據(jù)結(jié)構(gòu)【2022/11/23template<classT>classSortableList{//可排序表類public:SortableList(intmSize);~SortableList();

private:

T*l;//指向動(dòng)態(tài)生成的一位數(shù)組

intmaxSize;intn;};2022/11/22template<classT>2022/11/235.3二分搜索2022/11/225.3二分搜索問(wèn)題在有序表（已按關(guān)鍵字值非減排序）中搜索給定元素的問(wèn)題。a0a0am-1amam+1an-2an-1……2022/11/23問(wèn)題a0a0am-1amam+1an-2an-1……20222022/11/235.3.1

分治法求解intSortableList<T>::BSearch(constT&x,intleft,intright)const說(shuō)明:

在范圍為[left,right]的表中搜索與x有相同關(guān)鍵字值的元素；如果存在該元素，則函數(shù)返回該元素在表中的位置，否則函數(shù)返回－1，表示搜索失敗。2022/11/225.3.1

分治法求解intSort2022/11/23【程序5－6】二分搜索算法框架template<classT>intSortableList<T>::BSearch(constT&x,intleft,intright)const{ if(left<=right){intm=Divide(left+right);if(x<l[m])returnBSearch(x,left,m-1); elseif(x>l[m])

returnBSearch(x,m+1,right); elsereturnm;}return-1;}2022/11/22【程序5－6】二分搜索算法框架2022/11/235.3.2

對(duì)半搜索

對(duì)半搜索對(duì)半搜索是一種二分搜索。設(shè)當(dāng)前搜索的子表為（aleft,aleft+1,…,aright），令

m=(left+right)/2

2022/11/225.3.2

對(duì)半搜索對(duì)半搜索2022/11/23【程序5－7】對(duì)半搜索遞歸算法template<classT>intSortableList<T>::BSearch(constT&x,intleft,intright)const{if(left<=right){

intm=(left+right)/2;if(x<l[m])returnBSearch(x,left,m-1); elseif(x>l[m])returnBSearch(x,m+1,right);elsereturnm;}return-1;}2022/11/22【程序5－7】對(duì)半搜索遞歸算法2022/11/23定理5－3對(duì)于n0，程序5－7的對(duì)半搜索遞歸函數(shù)BSearch是正確的。程序5-7是尾遞歸函數(shù)，易改為迭代形式參考程序5-82022/11/22定理5－32022/11/23//程序5-8：對(duì)半搜索的迭代算法template<classT>intSortableList<T>::BSearch1(constT&x)const{ intm,left=0,right=n-1; while(left<=right){ m=(left+right)/2; if(x<l[m])right=m-1; elseif(x>l[m])left=m+1; elsereturnm; //搜索成功

} return-1; //搜索失敗}2022/11/22//程序5-8：對(duì)半搜索的迭代算法2022/11/235.3.3

二叉判定樹(shù)

二分搜索過(guò)程的算法行為可以用一棵二叉樹(shù)來(lái)描述。通常稱這棵描述搜索算法執(zhí)行過(guò)程的二叉樹(shù)為二叉判定樹(shù)(binarydecisiontree)。2022/11/225.3.3

二叉判定樹(shù)二分搜索過(guò)程2022/11/23如何構(gòu)建二叉判定樹(shù)內(nèi)節(jié)點(diǎn)外節(jié)點(diǎn)2022/11/22如何構(gòu)建二叉判定樹(shù)內(nèi)節(jié)點(diǎn)外節(jié)點(diǎn)2022/11/23性質(zhì)5－1

具有n個(gè)內(nèi)結(jié)點(diǎn)的對(duì)半搜索二叉判定樹(shù)的左子樹(shù)上有(n-1)/2個(gè)內(nèi)結(jié)點(diǎn)，右子樹(shù)上有n/2個(gè)內(nèi)結(jié)點(diǎn)。

性質(zhì)5－2

具有n(n>0）個(gè)內(nèi)結(jié)點(diǎn)的二叉判定樹(shù)的高度為logn+1

（不計(jì)外結(jié)點(diǎn)）。

2022/11/22性質(zhì)5－12022/11/23性質(zhì)5－3

若n=2h-1，則對(duì)半搜索二叉判定樹(shù)是滿二叉樹(shù)。

性質(zhì)5－4

若n=2h-1，則對(duì)半搜索二叉判定樹(shù)的外結(jié)點(diǎn)均在h+1層上，否則，在第h或h+1層上，h=logn+1。

2022/11/22性質(zhì)5－32022/11/23定理5－4

對(duì)半搜索算法在成功搜索的情況下，關(guān)鍵字值之間的比較次數(shù)不超過(guò)logn+1。對(duì)于不成功的搜索，算法需要作logn或logn+1次比較。定理5－5

對(duì)半搜索算法在搜索成功時(shí)的平均時(shí)間復(fù)雜度為(logn)。

對(duì)半搜索是一個(gè)最優(yōu)算法2022/11/22定理5－4對(duì)半搜索是一個(gè)最優(yōu)算法2022/11/235.3.4搜索算法的時(shí)間下界

定理5－6

在一個(gè)有n個(gè)元素的集合中，通過(guò)關(guān)鍵字值之間的比較，搜索指定關(guān)鍵字值的元素，任意這樣的算法在最壞情況下至少需要作log

n+1次比較。2022/11/225.3.4搜索算法的時(shí)間下界定理5－2022/11/23練習(xí)1編寫程序?qū)崿F(xiàn)三分搜索算法，分析其時(shí)間復(fù)雜度，并與對(duì)半搜索算法的時(shí)間性能進(jìn)行比較。2022/11/22練習(xí)1編寫程序?qū)崿F(xiàn)三分搜索算法，分析其時(shí)2022/11/235.4排序問(wèn)題

2022/11/225.4排序問(wèn)題2022/11/23

問(wèn)題排序是將一個(gè)元素序列調(diào)整為按指定關(guān)鍵字值的遞增（或遞減）次序排列的有序序列。2022/11/22問(wèn)題2022/11/235.4.1

合并排序

合并兩個(gè)有序序列

兩路合并排序的基本運(yùn)算是把兩個(gè)有序序列合并成一個(gè)有序序列。

2022/11/225.4.1

合并排序合并兩個(gè)有序序2022/11/23【程序5－9】Merge函數(shù)template<classT>voidSortableList<T>::Merge(intleft,intmid,intright){ T*temp=newT[right-left+1];inti=left,j=mid+1,k=0;while((i<=mid)&&(j<=right)) if(l[i]<=l[j])temp[k++]=l[i++];elsetemp[k++]=l[j++];while(i<=mid)temp[k++]=l[i++];while(j<=right)temp[k++]=l[j++]; for(i=0,k=left;k<=right;)l[k++]=temp[i++];}時(shí)間復(fù)雜度分析？2022/11/22【程序5－9】Merge函數(shù)時(shí)間復(fù)雜度2022/11/232022/11/222022/11/23

分治法求解將待排序的元素序列一分為二分，得到兩個(gè)長(zhǎng)度基本相等的子序列；然后對(duì)兩個(gè)子序列分別排序，如果子序列較長(zhǎng)，還可繼續(xù)細(xì)分，直到子序列的長(zhǎng)度不超過(guò)1為止；當(dāng)分解所得的子序列已排列有序，可以將兩個(gè)有序子序列，合并成一個(gè)有序子序列---合并排序2022/11/22分治法求解---合并排序2022/11/23【程序5－10】?jī)陕泛喜⑴判騮emplate<classT>voidSortableList<T>::MergeSort(intleft,intright){if(left<right){intmid=(left+right)/2;MergeSort(left,mid);MergeSort(mid+1,right);Merge(left,mid,right);}}2022/11/22【程序5－10】?jī)陕泛喜⑴判?022/11/23template<classT>voidSortableList<T>::MergeSort(){ MergeSort(0,n-1);}2022/11/22template<classT>2022/11/232022/11/222022/11/23

性能分析合并排序遞歸算法的時(shí)間復(fù)雜度為O(nlog

n)。2022/11/22性能分析2022/11/235.4.2

快速排序快速排序采用一種特殊的分劃操作對(duì)排序問(wèn)題進(jìn)行分解，其分解方法是：在待排序的序列(K0,K1,…,Kn-1)中選擇一個(gè)元素作為分劃元素，也稱為主元（pivot）。不妨假定選擇K為主元。經(jīng)過(guò)一趟特殊的分劃處理將原序列中的元素重新排列，使得以主元為軸心，將序列分成左右兩個(gè)子序列。主元左測(cè)子序列中所有元素都不大于主元，主元右測(cè)子序列中所有元素都大于主元。2022/11/225.4.2

快速排序快速排序采用一種2022/11/23

分劃操作2022/11/22分劃操作2022/11/23【程序5－11】

分劃函數(shù)template<classT>intSortableList<T>::Partition(intleft,intright){//前置條件：leftright inti=left,j=right+1;//初始主元放在最左邊do{doi++;while(l[i]<=l[left]);doj--;while(l[j]>l[left]);if(i<j)Swap(i,j);//交換

}while(i<j); Swap(left,j); //主元作為分界線 returnj;//返回主元位置}2022/11/22【程序5－11】分劃函數(shù)2022/11/23快速排序算法2022/11/22快速排序算法2022/11/23【程序5－12】快速排序template<classT>voidSortableList<T>::QuickSort(){QuickSort(0,n-1);}template<classT>voidSortableList<T>::QuickSort(intleft,intright){ if(left<right){intj=Partition(left,right);QuickSort(left,j-1); QuickSort(j+1,right); }}2022/11/22【程序5－12】快速排序2022/11/23

時(shí)間分析存在的最壞情況存在的最好情況最壞情況時(shí)間

W(n)W(n-1)+n+1

W(n-2)+(n+1)+n

W(1)+(n+1)++3=O(n2)

2022/11/22時(shí)間分析2022/11/23平均情況時(shí)間

2022/11/22平均情況時(shí)間2022/11/232022/11/222022/11/235.4.3排序算法的時(shí)間下界定理5－7

任何一個(gè)通過(guò)關(guān)鍵字值比較對(duì)n個(gè)元素進(jìn)行排序的算法，在最壞情況下，至少需作（n/4）log

n次比較。2022/11/225.4.3排序算法的時(shí)間下界定理5合并排序與快速排序比較1.基本思想2.劃分與組合方法的區(qū)別3.時(shí)間復(fù)雜度2022/11/23合并排序與快速排序比較1.基本思想2022/11/222022/11/235.5選擇問(wèn)題

2022/11/225.5選擇問(wèn)題2022/11/23問(wèn)題選擇問(wèn)題（selectproblem）是指在n個(gè)元素的集合中，選出某個(gè)元素值大小在集合中處于第k位的元素，即所謂的求第k小元素問(wèn)題(kth-smallest)。

2022/11/22問(wèn)題2022/11/235.5.1

分治法求解

設(shè)原表長(zhǎng)度為n，假定經(jīng)過(guò)一趟分劃，分成兩個(gè)左右子表，其中左子表是主元及其左邊元素的子表，設(shè)其長(zhǎng)度為p，右子表是主元右邊元素的子表。那么，若k=p，則主元就是第k小元素；否則若k<p，第k小元素必定在左子表中，需求解的子問(wèn)題成為在左子表中求第k小元素；若k>p，則第k小元素必定在右子表中，需求解的子問(wèn)題成為在右子表中求第k-p小元素。2022/11/225.5.1

分治法求解設(shè)原表長(zhǎng)度為n2022/11/235.5.2

隨機(jī)選擇主元

隨機(jī)選主元算法

假定表中元素各不相同，并且隨機(jī)選擇主元，即在下標(biāo)區(qū)間[left,right]中隨機(jī)選擇一個(gè)下標(biāo)r，以該下標(biāo)處的元素為主元。2022/11/225.5.2

隨機(jī)選擇主元隨機(jī)選主元算2022/11/23

【程序5－13】Select函數(shù)，元素集合為ltemplate<classT>ResultCodeSortableList<T>::Select1(T&x,intk){ //在l中找到第k大元素，通過(guò)x返回if(n<=0||k>n||k<=0)returnOutOfBounds;intleft=0,right=n;l[n]=INFTY;do{

intj=rand()%(right-left+1)+left;

//確定主元

Swap(left,j);

j=Partition(left,right);//劃分

if(k==j+1){x=l[j];returnSuccess;} elseif(k<j+1)right=j; elseleft=j+1; }while(true);}2022/11/22【程序5－13】Select函數(shù)，2022/11/23定理5