算法-第6章算法分析与问题的计算复杂度ppt课件.ppt

《算法-第6章算法分析与问题的计算复杂度ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、6.1平凡下界6.2直接计数求解该问题所需要的最少运算6.3决策树6.4检索算法的时间复杂度分析6.5排序算法的时间复杂度分析冒泡排序、堆排序、排序算法的决策树与时间复杂度下界6.6选择算法的时间复杂度分析找最大和最小问题、找第二大问题、找中位数的问题6.7通过归约确认问题计算复杂度的下界第6章算法分析与问题的计算复杂度2寻找最优算法的途径(1)设计算法A,求W(n)，得到算法类最坏情况下时间复杂度的一个上界(2)寻找函数F(n),使得对任何算法都存在一个规模为n的输入并且该算法在这个输入下至少要做F(n)次基本运算，得到该算法类最坏情况下时间复杂度的一个下界(3)如果W(n)=F(n)或

2、W(n)=(F(n)),则A是最优的.(4)如果W(n)>F(n),A不是最优的或者F(n)的下界过低.改进A或设计新算法A’使得W’(n)F(n).重复以上两步,最终得到W’(n)=F’(n)或者W’(n)=(F’(n))6.1平凡下界算法的输入规模和输出规模是它的平凡下界例6.1问题：写出所有的n阶置换求解的时间复杂度下界为(n!)例6.2问题：求n次实系数多项式多项式在给定x的值求解的时间复杂度下界为(n)例6.3问题：求两个nn矩阵的乘积求解的时间复杂度下界是(n2)例6.4问题：货郎问题求解的时间复杂度下界是(n2

3、)6.2直接计数最少运算数例6.5找最大W(n)=n-1以比较作为基本运算的算法类的上界：n-1算法Findmax输入数组L,项数n1输出L中的最大项MAX1.MAXL(1);i2;2.whileindo3.ifMAX

4、t层至多2t个结点（根为0层）命题6.2深度为d的二叉树至多2d+1-1个结点.命题6.3n个结点的二叉树的深度至少为logn.命题6.4设t为二叉树的树叶个数，d为树深，如果树的每个内结点都有2个儿子，则t2d.d层x个t-x个Tt-x+x/2个T’归纳法：d=0,命题为真.假设对小于d的深度为真，设T深度为d，树叶数t.取走T的d层树叶，得到T’.T’的深度为d1，树叶数t’。t’=(tx)+x/2=t–x/2，x2dt=t’+x/22d1+2d1=2d7算法顺序捡索输入:L,x输出:j1.j12.whilejnandL(j)xdojj+13.ifj>nthe

5、nj0分析：设x在L中每个位置和空隙的概率都是1/(2n+1)W(n)=nA(n)=[(1+2+...+n)+n(n+1)]/(2n+1)3n/4.6.4检索算法时间复杂度分析检索问题:给定按递增顺序排列的数组L(项数n1)和数x，如果x在L中,输出x的下标;否则输出0.8定理6.1W(n)=logn+1n1证对n归纳n=1时,左=W(1)=1,右=log1+1=1.假设对一切k,1k

6、k=2k1+n+1其中2k1为x在表中做k次比较的输入个数二分捡索的平均时间复杂度10求和11捡索问题的决策树设A是一个捡索算法,对于给定输入规模n,A的一棵决策树是一棵二叉树,其结点被标记为1,2,...,n,且标记规则是:(1)根据算法A，首先与x比较的L的项的下标标记为树根.(2)假设某结点被标记为i,i的左儿子是：当xL(i)时，算法A下一步与x比较的项的下标若xL(i)时算法A停止,则i没有右儿子.12改进顺序捡索算法和二分捡索算法的决策树，n=15给定输入,算法A将

7、从根开始,沿一条路径前进,直到某个结点为止.所执行的基本运算次数是这条路径的结点个数.最坏情况下的基本运算次数是树的深度+1.1231415841221356791011141315实例13检索问题的复杂度分析定理6.2对于任何一个搜索算法存在某个规模为n的输入使得该算法至少要做logn+1次比较.证由命题3,n个结点的决策树的深度d至少为logn,故W(n)=d+1=logn+1.结论:对于有序表搜索问题,