计算机算法基础2

《计算机算法基础2》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、计算机算法基础(2014.9)何琨brooklet60@gmail.com华中科技大学计算机学院2014/10/23算法：求解问题的一组规则检索问题分治策略排序问题发现贪心策略路径问题规则的设计设计策略动态规划最优化问题指导检索与周游遍历问题回溯与分支限界…….形成算法产生算法设计的指导思想和基本规律第二章分治法（DivideandConquer)——“分”而治之2.1一般方法2.2二分检索2.3找最大最小元素2.6选择问题2.7Strassen矩阵乘法注：2.4归并分类2.5快速分类不讲第二章分治法（DivideandConquer)

2、——“分”而治之2.1一般方法2.2二分检索2.3找最大最小元素2.6选择问题2.7Strassen矩阵乘法1.基本思想一个难以直接解决的、规模较大问题若干个规模较小、较容易解决的、性质相同的子问题分别解决这些子问题合并子问题的解从而得到原问题的解注意：子问题是相互独立的，否则存在重复计算常见的二分法规模为n的问题规模为n/2的子问题1规模为n/2的子问题2子问题1的解子问题2的解原始问题的解2.分治策略的抽象化控制过程——二分策略算法2.1分治策略的抽象化控制注：procedureDANDC(p,q)k=2:二分是最常用的分解

3、策略；globaln,A(1:n);SMALL(p,q)：布尔函数，判断输入规模q-p+1是否足够小而无需再integerm,p,q;//1≤p≤q≤n//进一步分就可求解；ifSMALL(p,q)G(p,q)：当SMALL(p,q)为真时，thenreturn(G(p,q))对输入规模为q-p+1的子问题求解；elseDIVIDE(p.q)：当规模q-p+1还较m←DIVIDE(p,q)//p≤m＜q//大时，对规模为q-p+1的子问题进return(COMBINE(DANDC(p,m),一步分解，返回值为[p,q]区间进一步的分割点；D

4、ANDC(m+1,q)))COMBINE(x,y)：子结果的合并函endif数，将区间[p,m]和[m+1,q]上的子endDANDC问题的解合并成区间[p,q]上的“较完整”的解。当p=1,q=n时，最初的调用：DANDC(1,n)就得到整个问题的解。DANDC的计算时间若所分成的两个子问题的规模大致相等，则DANDC总的计算时间可用递归关系式表示如下：g(n)n足够小T(n)=2T(n/2)+f(n)否则注：T(n)：表示输入规模为n时的DANDC计算时间g(n)：表示对足够小的输入规模直接求解的计算时间f(n)：表示COMBINE

5、对两个子区间的子结果进行合并的时间（该公式针对具体问题有各种不同的变形）补充：递归式的时间复杂度分析Mastermethod(主方法)1)ndTn()aT()On()b其中a>=1,b>=1,a,b,d取值与n无关2)n足够小时：Tn()O(1)ddOn(log),n若abddTn()On(),若ablogadOn(b),若ab例1:解递归式T(n)9T(n/3)n例2.解递归式T(n)T(2n/3)1ddOn(log),n若abddTn()On(),若ablogadOn(b),若ab

6、例1:解递归式T(n)9T(n/3)n分析：a=9，b=3，d=1，则2T(n)(n)例2.解递归式T(n)T(2n/3)1分析：a=1，b=3/2，d=0，则Tn()(log)nddOn(log),n若abddTn()On(),若ablogadOn(b),若ab第二章分治法（DivideandConquer)——“分”而治之2.1一般方法2.2二分检索2.3找最大最小元素2.6选择问题2.7Strassen矩阵乘法2.2二分检索——折半查找1.问题的描述有序表上的检索问题：已知一个按非降次序排列的

7、元素表a,a,…,a，判定某给定的元素x是否在该表中出现。12n若是，则找出x在表中的位置并返回其所在位置的下标若非，则返回0值。Q:顺序检索的平均时间和最坏时间？问题的形式描述：I=(n,a,a,…,a,x)12n问题分解：选取下标k，由此将I分解为3个子问题：I1=(k-1,a1,a2,…,ak-1,x)规模较大I2=(1,ak,x)规模足够小I3=(n-k,ak+1,a2,…,an,x)规模较大对于I2，若ak=x，则有解k，对I1、I3不用再求解；否则，若xa，则只在I中求解，对

8、I不用求解；k31对I1、I3的求解可再次采用分治方法求解递归过程2.二分检索二分检索：每次选取中间元素的下标算法2.3二分检索pro