算法设计与分析

2024/10/11第2部分算法设计策略第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]; }}时间复杂度？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

设有n个元素的表，假定n是2的幂，即n=2k，k是正整数，程序5－5在最好、平均和最坏情况下的比较次数都为3n/2–2。设n=2k，易解2024/10/115.1一般方法

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

分治法顾名思义就是分而治之。一个问题能够用分治法求解的要素是：第一，问题能够按照某种方式分解成若干个规模较小、相互独立且与原问题类型相同的子问题；第二，子问题足够小时可以直接求解；第三，能够将子问题的解组合成原问题的解。由于分治法要求分解成同类子问题，并允许不断分解，使问题规模逐步减小，最终可用已知的方法求解足够小的问题，因此，分治法求解很自然导致一个递归算法。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算法分析

采用分治法求解问题通常得到一个递归算法。如果较大的问题被分解成同样大小的几部分，那么分析相应算法的执行时间，往往可得到如下的递推关系式：T(n)=aT(n/b)+cnk，T(1)=c

2024/10/11定理5-1设a,b,c和k为常数，T(n)=aT(n/b)+cnk，T(1)=c，则，

2024/10/11n=bm2024/10/11设r=bk/a，下面分三种情况计算。（1）若r<1，则

所以（2）若r=1，则

所以（3）若r>1，则

所以2024/10/115.1.3

排序问题数据结构【程序5－3】可排序表类template<classK,classD>structE{//可排序表中元素的类型

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

private:

T*l;//指向动态生成的一位数组

intmaxSize;intn;};2024/10/115.3二分搜索问题在有序表（已按关键字值非减排序）中搜索给定元素的问题。a0a0am-1amam+1an-2an-1……2024/10/112024/10/115.3.1

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

在范围为[left,right]的表中搜索与x有相同关键字值的元素；如果存在该元素，则函数返回该元素在表中的位置，否则函数返回－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

对半搜索

对半搜索对半搜索是一种二分搜索。设当前搜索的子表为（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的对半搜索递归函数BSearch是正确的。程序5-7是尾递归函数，易改为迭代形式参考程序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

二叉判定树

二分搜索过程的算法行为可以用一棵二叉树来描述。通常称这棵描述搜索算法执行过程的二叉树为二叉判定树(binarydecisiontree)。2024/10/11如何构建二叉判定树内节点外节点2024/10/11性质5－1

具有n个内结点的对半搜索二叉判定树的左子树上有

(n-1)/2

个内结点，右子树上有

n/2

个内结点。

性质5－2

具有n(n>0）个内结点的二叉判定树的高度为

logn

+1

（不计外结点）。

2024/10/11性质5－3

若n=2h-1，则对半搜索二叉判定树是满二叉树。

性质5－4

若n=2h-1，则对半搜索二叉判定树的外结点均在h+1层上，否则，在第h或h+1层上，h=

logn

+1。

2024/10/11定理5－4

对半搜索算法在成功搜索的情况下，关键字值之间的比较次数不超过

logn

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

logn

或

logn

+1次比较。定理5－5

对半搜索算法在搜索成功时的平均时间复杂度为

(logn)。

对半搜索是一个最优算法2024/10/115.3.4搜索算法的时间下界

定理5－6

在一个有n个元素的集合中，通过关键字值之间的比较，搜索指定关键字值的元素，任意这样的算法在最坏情况下至少需要作

log

n

+1次比较。2024/10/11练习1编写程序实现三分搜索算法，分析其时间复杂度，并与对半搜索算法的时间性能进行比较。2024/10/115.4排序问题

2024/10/11

问题排序是将一个元素序列调整为按指定关键字值的递增（或递减）次序排列的有序序列。2024/10/115.4.1

合并排序

合并两个有序序列

两路合并排序的基本运算是把两个有序序列合并成一个有序序列。

2024/10/11【程序5－9】Merge函数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++];}时间复杂度分析？2024/10/112024/10/11

分治法求解将待排序的元素序列一分为二分，得到两个长度基本相等的子序列；然后对两个子序列分别排序，如果子序列较长，还可继续细分，直到子序列的长度不超过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

性能分析合并排序递归算法的时间复杂度为O(nlog

n)。2024/10/115.4.2

快速排序快速排序采用一种特殊的分划操作对排序问题进行分解，其分解方法是：在待排序的序列(K0,K1,…,Kn-1)中选择一个元素作为分划元素，也称为主元（pivot）。不妨假定选择K

为主元。经过一趟特殊的分划处理将原序列中的元素重新排列，使得以主元为轴心，将序列分成左右两个子序列。主元左测子序列中所有元素都不大于主元，主元右测子序列中所有元素都大于主元。2024/10/11

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

分划函数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

任何一个通过关键字值比较对n个元素进行排序的算法，在最坏情况下，至少需作（n/4）log

n次比较。合并排序与快速排序比较1.基本思想2.划分与组合方法的区别3.时间复杂度2024/10/112024/10/115.5选择问题

2024/10/11问题选择问题（selectproblem）是指在n个元素的集合中，选出某个元素值大小在集合中处于第k位的元素，即所谓的求第k小元素问题(kth-smallest)。

2024/10/115.5.1

分治法求解

设原表长度为n，假定经过一趟分划，分成两个左右子表，其中左子表是主元及其左边元素的子表，设其长度为p，右子表是主元右边元素的子表。那么，若k=p，则主元就是第k小元素；否则若k<p，第k小元素必定在左子表中，需求解的子问题成为在左子表中求第k小元素；若k>p，则第k小元素必定在右子表中，需求解的子问题成为在右子表中求第k-p小元素。2024/10/115.5.2

随机选择主元

随机选主元算法

假定表中元素各不相同，并且随机选择主元，即在下标区间[left,right]中随机选择一个下标r，以该下标处的元素为主元。2024/10/11

【程序5－13】Select函数，元素集合为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)。算法的最坏情况时间复杂度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]范围内的元素分组，每组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);