第八单元简单算法时空分析

《第八单元简单算法时空分析》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、第八单元简单算法时空分析8.1算法分析的概念算法分析是指通过数学方法对一个算法的时间效率和空间效率经行评估，并判断该算法的优劣。如果算法A的时空复杂度均低于算法B,那么我们认为算法A优于算法B。有时也有以空间换时间或者以时间换空间的算法，比如暴搜和记忆化搜索，前者是以吋间换空间的算法，而后者是以空间换时间。算法的设计要求：•正确性+程序不含语法错误；♦程序对几组输入数据能够得出满足规格耍求的结果；♦程序对梢心选择的、典型的、苛刻的、带有刁难性的儿组输入数据能够得出满足规格要求的结果；+程序对一切合法的输入数据都能产生满足规格要求的结果。•可

2、读性：有助于阅读和交流、有助于对算法的理解、有助于对算法的调试和修改。•高效率和低存储：处理速度快、存储容虽小。8.2时间复杂度时间复杂度，从名字就可以知道，它表示的是算法运行的时间效率。一个算法运行所耗费的时间，除了与所用的计算软、硬件环境有关外，主要取决于算法中指令重复执行的次数，即语句的频度相关。一个算法中所冇语句的频度z和构成了该算法的运行时间。以下为儿个代码例子，我们依次分析它们的基本操作次数，并尝试分析时间复杂度。【代码分析例1】fact=1;for(inti=l;i<=n;i++)fact=fact*i;—•次乘法为-•个基本

3、操作，忽略i改变的吋间。共f(n)=n次基木操作。吋间复朵度为n【代码分析的例子2】sum=0;for(inti=l;iv二n;i++)for(intj=l;j<=n;i++)〃这里的a[i][j]是二维数组，我们认为a数组存储了n^n个变量。sum=sum+a[i][j];基木操作：加法，乘法，忽略循环变最i和j的改变时间，共"2次基木操作。时间复杂度为於2【代码分析的例子3】这段代码实现的是1!+2!+……+n!sum=0;for(inti=l;i<=n;i++)fact=fact*jfact=l;for(intj=l;j<=i;i++

4、)sum:=sum+fact;第i次循环执行了i个操作，总时间复杂度为1+2+3+…+n二n(n+l)/2。这个式了我们可以约等于22/2。如果式子再长一点，怎么办？比较【例2］和【例3】，【例2］执行了f(n)E2次基本操作,【例3］执行了g(n)="2/2次基本操作。那个算法好呢？算法二好，因为g(n)

5、2/2。我们知道，它们的增长情况一样。如何表示“增长情况”？把f(n)和g(n)变成“渐进”形式，然后肓接比较。如何变成“渐进'形式？1)只保留最“大巧页；2)忽略系数例1：3nA4+8nA2+n+2的渐进时间复杂度为nA4例2：2A(n+l)+n*100+5的渐进时间复杂度为2An(为什么n+1变成了n?)有时候复杂度分析不是万能的，或者说有时候不知道最坏情况是多少。我们看一下OJ【P1029】一个数n,如果它是奇数则变换到3n+l,否则变换到n/2。给一个数n,不停的变换下去，经过几步变成1?你知道它的运行时间吗?!反正我不知道，这是个

6、著名的停机问题所以，我们在分析时间复杂度的时候，只分析上限，而不管实际运行时间。若n充分大时

7、f(n)

8、v=c

9、g(n)

10、,其中c为某常数。记f(n)=O(g(n)),表示g(n)为f(n)的渐进上限例1：5nA2+3n+l=0(nA2)例2：223=0(23)山于上限有无限多个，我们希望它尽量粕确。否则我们的分析就过于悲观了，实际算法没那么糟糕。这就是我们常说的时间复杂度，一般用最坏的时间复杂度来衡最一个程序的效率。常见的复杂度等级：绝大多数算法都定多项式算法OO(nAt),t是常数OO(log(t)n),t是常数OO(loglogn),

11、奇怪吗？后面会遇到一个O两个多项式时间复杂度的积仍是多项式的复杂度效率排序，越靠左边，效率越高。0(1)

12、表示i的N次幕。(指数级)O(N!)：表示N的阶乘，即N!=1*2*3*...*No(阶乘级)强调：这里的logn的对数底不是10,而是2,也就是10g2(n)o这个是要记住的。