算法設(shè)計與分析

2024/10/11第2部分算法設(shè)計策略第5章分治法

2024/10/115.2

求最大最小元5.1

分治法的基本思想5.3

二分搜索5.4

排序問題5.5選擇問題5.6斯特拉森矩陣乘法

2024/10/115.2求最大最小元

2024/10/11

問題在一個元素集合L中尋找最大元素和最小元素的問題。一般方法？2024/10/115.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]; }}時間復(fù)雜度？2024/10/11【程序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)//只有兩個元素時

if(l[i]<l[j]){ max=l[j];min=l[i]; } else{ max=l[i];min=l[j]; } 2024/10/11 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; }}

2024/10/115.2.2時間分析定理5－2

設(shè)有n個元素的表，假定n是2的冪，即n=2k，k是正整數(shù)，程序5－5在最好、平均和最壞情況下的比較次數(shù)都為3n/2–2。設(shè)n=2k，易解2024/10/115.1一般方法

2024/10/115.1.1分治法的基本思想

分治法顧名思義就是分而治之。一個問題能夠用分治法求解的要素是：第一，問題能夠按照某種方式分解成若干個規(guī)模較小、相互獨立且與原問題類型相同的子問題；第二，子問題足夠小時可以直接求解；第三，能夠?qū)⒆訂栴}的解組合成原問題的解。由于分治法要求分解成同類子問題，并允許不斷分解，使問題規(guī)模逐步減小，最終可用已知的方法求解足夠小的問題，因此，分治法求解很自然導(dǎo)致一個遞歸算法。2024/10/11【程序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)); }}2024/10/11【程序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)); }}2024/10/115.1.2算法分析

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

2024/10/11定理5-1設(shè)a,b,c和k為常數(shù)，T(n)=aT(n/b)+cnk，T(1)=c，則，

2024/10/11n=bm2024/10/11設(shè)r=bk/a，下面分三種情況計算。（1）若r<1，則

所以（2）若r=1，則

所以（3）若r>1，則

所以2024/10/115.1.3

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

operatorK()const{returnkey;}Kkey;Ddata;};2024/10/11template<classT>classSortableList{//可排序表類public:SortableList(intmSize);~SortableList();

private:

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

intmaxSize;intn;};2024/10/115.3二分搜索問題在有序表（已按關(guān)鍵字值非減排序）中搜索給定元素的問題。a0a0am-1amam+1an-2an-1……2024/10/112024/10/115.3.1

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

在范圍為[left,right]的表中搜索與x有相同關(guān)鍵字值的元素；如果存在該元素，則函數(shù)返回該元素在表中的位置，否則函數(shù)返回－1，表示搜索失敗。2024/10/11【程序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;}2024/10/115.3.2

對半搜索

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

m=(left+right)/2

2024/10/11【程序5－7】對半搜索遞歸算法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;}2024/10/11定理5－3對于n

0，程序5－7的對半搜索遞歸函數(shù)BSearch是正確的。程序5-7是尾遞歸函數(shù)，易改為迭代形式參考程序5-82024/10/11//程序5-8：對半搜索的迭代算法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; //搜索失敗}2024/10/115.3.3

二叉判定樹

二分搜索過程的算法行為可以用一棵二叉樹來描述。通常稱這棵描述搜索算法執(zhí)行過程的二叉樹為二叉判定樹(binarydecisiontree)。2024/10/11如何構(gòu)建二叉判定樹內(nèi)節(jié)點外節(jié)點2024/10/11性質(zhì)5－1

具有n個內(nèi)結(jié)點的對半搜索二叉判定樹的左子樹上有

(n-1)/2

個內(nèi)結(jié)點，右子樹上有

n/2

個內(nèi)結(jié)點。

性質(zhì)5－2

具有n(n>0）個內(nèi)結(jié)點的二叉判定樹的高度為

logn

+1

（不計外結(jié)點）。

2024/10/11性質(zhì)5－3

若n=2h-1，則對半搜索二叉判定樹是滿二叉樹。

性質(zhì)5－4

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

logn

+1。

2024/10/11定理5－4

對半搜索算法在成功搜索的情況下，關(guān)鍵字值之間的比較次數(shù)不超過

logn

+1。對于不成功的搜索，算法需要作

logn

或

logn

+1次比較。定理5－5

對半搜索算法在搜索成功時的平均時間復(fù)雜度為

(logn)。

對半搜索是一個最優(yōu)算法2024/10/115.3.4搜索算法的時間下界

定理5－6

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

log

n

+1次比較。2024/10/11練習1編寫程序?qū)崿F(xiàn)三分搜索算法，分析其時間復(fù)雜度，并與對半搜索算法的時間性能進行比較。2024/10/115.4排序問題

2024/10/11

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

合并排序

合并兩個有序序列

兩路合并排序的基本運算是把兩個有序序列合并成一個有序序列。

2024/10/11【程序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++];}時間復(fù)雜度分析？2024/10/112024/10/11

分治法求解將待排序的元素序列一分為二分，得到兩個長度基本相等的子序列；然后對兩個子序列分別排序，如果子序列較長，還可繼續(xù)細分，直到子序列的長度不超過1為止；當分解所得的子序列已排列有序，可以將兩個有序子序列，合并成一個有序子序列---合并排序2024/10/11【程序5－10】兩路合并排序template<classT>voidSortableList<T>::MergeSort(intleft,intright){if(left<right){intmid=(left+right)/2;MergeSort(left,mid);MergeSort(mid+1,right);Merge(left,mid,right);}}2024/10/11template<classT>voidSortableList<T>::MergeSort(){ MergeSort(0,n-1);}2024/10/112024/10/11

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

n)。2024/10/115.4.2

快速排序快速排序采用一種特殊的分劃操作對排序問題進行分解，其分解方法是：在待排序的序列(K0,K1,…,Kn-1)中選擇一個元素作為分劃元素，也稱為主元（pivot）。不妨假定選擇K

為主元。經(jīng)過一趟特殊的分劃處理將原序列中的元素重新排列，使得以主元為軸心，將序列分成左右兩個子序列。主元左測子序列中所有元素都不大于主元，主元右測子序列中所有元素都大于主元。2024/10/11

分劃操作2024/10/11【程序5－11】

分劃函數(shù)template<classT>intSortableList<T>::Partition(intleft,intright){//前置條件：left

right 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;//返回主元位置}2024/10/11快速排序算法2024/10/11【程序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); }}2024/10/11

時間分析存在的最壞情況存在的最好情況最壞情況時間

W(n)

W(n-1)+n+1

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

W(1)+(n+1)+

+3=O(n2)

2024/10/11平均情況時間

2024/10/112024/10/115.4.3排序算法的時間下界定理5－7

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

n次比較。合并排序與快速排序比較1.基本思想2.劃分與組合方法的區(qū)別3.時間復(fù)雜度2024/10/112024/10/115.5選擇問題

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

2024/10/115.5.1

分治法求解

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

隨機選擇主元

隨機選主元算法

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

【程序5－13】Select函數(shù)，元素集合為ltemplate<classT>ResultCodeSortableList<T>::Select1(T&x,intk){ //在l中找到第k大元素，通過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);}2024/10/11定理5－8

程序5－13的Select算法的平均時間A(n)=O(n)。算法的最壞情況時間復(fù)雜度O(n2)，？。2024/10/115.5.3

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

2024/10/112024/10/11

【程序5－14】線性時間選擇算法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;}

2024/10/11template<classT>intSortableList<T>::Select(intk,intleft,intright,intr){//對[left…right]范圍內(nèi)的元素分組，每組r個元素采用二次取中法，確定主元intn=right-left+1;if(n<=r){InsertSort(left,right);//直接排序

returnleft+k-1;

}2024/10/11for(inti=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);}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);