[理学]《算法设计与分析》第05章

《[理学]《算法设计与分析》第05章》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、算法设计与分析DeSignandAnalysisofAlgorithmsInC++“十一五”国家级规划教材陈慧南编著电子工业出版社第2部分算法设计策略第5章分治法5.1分治法的基本思想5.2求最大最小元5.3二分搜索5.4排序问题5.5选择问题5.6斯特拉森矩阵乘法5.1一般方法5.1.1分治法的基本思想分治法顾名思义就是分而治之。一个问题能够用分治法求解的要素是：第一，问题能够按照某种方式分解成若干个规模较小、相互独立且与原问题类型相同的子问题；第二，子问题足够小时可以直接求解；第三，能够将子问题的解组合成原问题的解。由于分

2、治法要求分解成同类子问题，并允许不断分解，使问题规模逐步减小，最终可用已知的方法求解足够小的问题，因此，分治法求解很自然导致一个递归算法。【程序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));}}【程序5-2】一分为二的分治法SolutionTypeDandC(in

3、tleft，intright){if(Small(left,right))returnS(left,right);else{intm=Divide(left，right);ReturnCombine(DandC(left，m)，DandC(m+1，right));}}5.1.2算法分析采用分治法求解问题通常得到一个递归算法。如果较大的问题被分解成同样大小的几部分，那么分析相应算法的执行时间，往往可得到如下的递推关系式：T(n)=aT(n/b)+cnk，T(1)=c定理5-1设a,b,c和k为常数，T(n)=aT(n/b)+cn

4、k，T(1)=c，则，设r=bk/a，下面分三种情况计算。（1）若r<1，则所以（2）若r=1，则所以（3）若r>1，则所以例如：(1)T(n)=2T(n/2)+na=2,b=2,k=1,a=bk所以T(n)=(nlog(n))(2)T(n)=4T(n/4)+n2a=4,b=4,k=2,abk所以T(n)=(n4)5.1.3数据结构【程序5－3】可排序表类templatestructE{//可排序

5、表中元素的类型operatorK()const{returnkey;}//重载类型转换运算符Kkey;//关键字可以比较大小Ddata;//其他数据};templateclassSortableList//可排序表类{public:SortableList(intmSize)//构造函数{maxSize=mSize;l=newT[maxSize];n=0;}~SortableList(){delete[]l;}//析构函数private:T*l;//定义动态一维数组intmaxSize;//线性表的最大表长

6、intn;//线性表的实际长度;}5.2求最大最小元问题在一个元素集合中寻找最大元素和最小元素的问题。5.2.1分治法求解【程序5－4】求最大最小元templatevoidSortableList::MaxMin(T&max,T&min)const{if(n==0)return;max=min=l[0];for(inti=1;imax)max=l[i];if(l[i]

7、latevoidSortableList::MaxMin(T&max,T&min)const{if(n==0)return;max=min=l[0];for(inti=1;imax)max=l[i];elseif(l[i]voidSortableList::MaxMin(inti,intj,T&max,T&min)con

8、st{Tmin1,max1;if(i==j)max=min=l[i];elseif(i==j-1)if(l[i]