第二讲 算法分析概要与线性表.ppt

《第二讲 算法分析概要与线性表.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、算法复杂度概念线性表（上）2008/02/19关于浮点数四则运算的定义2算法复杂度问题：一般是指问题随规模的增长算法所需消耗的运算时间和内存空间的增长趋势。因此不考虑计算机本身硬件的特质，一般也忽略算法所消耗的与问题规模无关的固定量的计算与空间。3如何描述增长趋势的高低？不考虑不变量：C+f(n)f(n)忽略不能与时俱进的因素kf(n)f(n)区分同类型的增长方式的不同量级f(n)=nkf(n)=nk+c专注增长趋势中最本质的区别Clognnnkkn(k>1)4算法复杂度的考察方法考察一个算法的复杂度，一般考察的

2、是当问题复杂度n的增加时，运算所需时间、空间代价f(n)的上下界。（Asymptoticupperorlowerbound）进一步而言，又分为最好情况、平均情况、最坏情况三种情况。通常最坏情况往往是我们最关注的。5算法复杂度的上界（大O表示法）大O表示法是用一个函数f(n)来描写算法复杂度的上界的表示方式。记为：O（f(n)）6大Θ表示法如果能同时找到算法复杂度的上下确界函数g(n)，f(n)。且g(n)=f(n)，则算法复杂度能更精确的表达为Θ(f(n))7算法复杂度的优化（fibonacci数列问题）刚开始（零年）1对一年

3、后1对二年后2对三年后3对…今年的兔子对数=前年已经有的兔子总数+去年的兔子数01234Fibonacci数列8采用展开递推公式的方法fib(5)fib(3)fib(4)+fib(1)fib(2)+fib(0)fib(1)+fib(2)fib(3)+fib(1)fib(2)+…从fib(n)开始，自顶向下逐层展开。直到fib(0)或fib(1)为止。然后逐层计算上去。…=1=1=1=19递归算法的运算复杂度分析fib(5)fib(3)fib(4)+T(n)=T(n-1)+T(n-2)+1T(1)=T(0)=1fib(1)fib

4、(2)+fib(0)fib(1)+fib(2)fib(3)+fib(1)fib(2)+…找出与n相关的函数=1=1=1=12n/2voidf2(intx,inty);voidf1(intx,inty){if(x>200)return;else{x=x+y;y=x-y;x=x-y;prin

5、tf("%d,",x);f2(x,y);}}voidf2(intx,inty){y=x+y;f1(x,y);}voidmain(){f1(0,1);}12Fibonacci数列的通项公式1/1=1,2/1=2,3/2=1·5,5/3=1·666...,8/5=1·6,13/8=1·62521/13=1·61538...黄金分割数T(n)=O(1.618n)13Fibonacci数列的矩阵表达11101110X=1+11+01+01+01110X=2+12+01+11+01110X=53321110n=fib(n+1)fib(n

6、)fib(n)fib(n-1)Howcome?14Fibonacci数列的矩阵表达11101110X=1+11+01+01+01110X=2+12+01+11+01110X=53321110n=fib(n+1)fib(n)fib(n)fib(n-1)Howcome?15Fibonacci数列的矩阵表达F1F01110X=0110XF2F1F1F01000+=F1F2F0F1+F20F10BCAB+11110n=fib(n+1)fib(n)fib(n)fib(n-1)16Recursivepowering（递归乘方法）1110n

7、n次矩阵乘法算法复杂度=O(n)=1110n/21110n/2x+[]1110n/2/21110n/2/2x+[]总共要多少层递归？=log2n算法复杂度=O(logn)17Recursivepowering（递归乘方法）1110nn次矩阵乘法算法复杂度=O(n)=1110n/21110n/2x+[]1110n/2/21110n/2/2x+[]总共要多少层递归？=log2n算法复杂度=O(logn)18Fibonacci数列算法的优化参考阅读：MIT教程第三讲T(n)=O(1.618n)=O(n)=O(logn)fib(110

8、)：1022次运算111次运算7次运算19算法设计技术贪心法：试图通过局部最优达到全局最优分治法：划分成小问题，各个求解回溯法：对多种可能性逐步试探，失败时回来选其它可能性动态规划法：多路经的求解方式分枝界限法：上下界+广度优先20算法与问题求解问题：为贫困地区儿童募捐