算法分析与设计2-算法分析技术

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

1、算法分析技术第三部分1、算法复杂性：它是度量算法计算难度的一种尺度，反映了算法消耗的资源情况。算法需要资源越多，其复杂性就越高；反之，算法需要资源越少，其复杂性就越小。时间复杂性（TimeComplexity）：如果问题的规模为n，解决这一问题的某算法在算法的输入为I时所需的时间为T(n,I)，T(n，I)称为算法的时间复杂性。3.1算法复杂性分析空间复杂性（SpaceComplexity）：如果问题的规模为n，解决这一问题的某算法在算法的输入为I时所需的空间为S(n,I)，S(n,I)称为算法的空间复杂性。算法分析（Al

2、gorithmAnalysis）:分析算法复杂性的过程；算法的最好时间复杂性：Tmin(n)=MinT(n,I)=T(n,I*)IDnDn是规模为n的合法输入的集合，I*是使算法的时间达到最小的一个输入；算法的复杂性除了与问题的规模有关外，在规模一定的情况下，输入的分布也会影响算法的复杂性。从而就有了最好、最坏、平均复杂性。3.1算法复杂性分析算法的最坏时间复杂性：Tmax(n)=MaxT(n,I)=T(n,I#)IDnDn是规模为n的合法输入的集合，I#是使算法的时间达到最大的一个输入；算法的平均时间复杂性：Tavg

3、(n)=P(I)T(n,I)IDnDn是规模为n的合法输入的集合,p(I)是输入I出现的概率。3.1算法复杂性分析对算法空间复杂性可以同样定义。实践证明，可操作性最好且最有实际价值的是最坏复杂性！注：输入规模的概念和具体问题有关，对有些问题来说，最自然的度量标准是输入中的元素个数（例如，排序）；对另一些问题其规模的最佳度量是输入数在二进制表示下的位数（例如整数相乘）；还有的问题需要用两个数表示输入规模（例如图的顶点数和边数）。3.1算法复杂性分析对于一个算法而言，在不同的执行时间内，它占用的内存空间量不一定相等，也就是

4、说，占用空间量y是时间x的函数，即y=f(x)。定义：时空积分=其中t是算法的运行时间。时空积可以综合评价算法的时间、空间性能。102030807060yx效率例如：一个算法的执行时间为30秒，前10秒算法占用60个字节，第2个10秒占用70个字节，最后10秒占用80个字节，则：时空积如图。60*10+70*10+80*10=2100(字节秒)2、问题的时间（空间）复杂性：假设问题有多个算法，所有算法的集合表示为，其中A是其中的一个算法，即A，它的时间（空间）复杂性表示为TA(n),问题的时间（空间）复杂性定义为：M

5、in(TA(n))。A即最优算法的时间（空间）复杂性为该问题的时间复杂性。3.1算法复杂性分析3.1算法复杂性分析最初，我们希望精确计算出算法的复杂性（用多少时间、占多少空间）。但是，很难（可比性差），也没有必要！精确测算出算法的性能指标是很难的，因为：（1）把两个或多个算法都写出程序代码须花费很大的时间和精力；（2）可能会因为程序写的“好”而没有体现出算法的真正质量，特别是程序员对算法有偏见时；（3）测试环境和测试数据的选择很难对各个算法公正；（4）你觉得好的算法也不一定达到要求，要重复设计算法、写代码、测试。3.1

6、算法复杂性分析但是，值得注意的是无论是操作计数还是执行步数都不能够非常准确地描述时间复杂性，特别是在需要比较时。例如:t1(n)=10n2+20n-100t2(n)=1000n+500哪个更好？？然后，我们又提出用评估的方法，抓主要矛盾和核心的东西，用统计基本操作或步数来估计复杂性。于是，既然我们的目的是为了比较，就应该将注意力集中在被比较的对象之间最主要的差别。如果两个程序执行步数分别是3n+2和3n+20，则这两个程序的时间复杂性不会有太大的差别，即使这两个程序的每个执行步操作数可能有所不同，这两个程序的时间复杂性至多

7、相差一个常数倍。最后，就有了一个关注点，算法性能的增长率！3.1算法复杂性分析算法的增长率(growthrate)：是指当输入增长时，算法代价的增长速率。具体就体现在两个函数的变化趋势上。T(n)=f(n)S(n)=g(n)线性增长率(lineargrowthrate)二次增长率(quadraticgrowthrate)指数增长率(exponentialgrowthrate)3.1算法复杂性分析换更快的计算机，还是换更快的算法？从增长率可以看出：算法不同，当计算机速度提高时，你得到的解决问题规模的增益是不同的！例如，当计算

8、机的运行速度是提高为原来的10倍时，不同的算法在解决问题的规模上得到的收益是有很大不同的。f(n)nn’变化n’/n10n100010000n’=10n1020n5005000n’=10n105nlogn2501842n