《算法效率分析基础》PPT课件.ppt

《《算法效率分析基础》PPT课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、算法设计与分析计算机与信息学院2使用教材使用教材作者：（美）AnanyLevitin译者：潘彦出版社：清华大学丛书名：国外经典教材·计算机科学与技术第2章算法效率分析基础算法效率分析框架渐进符号和基本效率类型非递归算法效率分析递归算法效率分析4算法效率分析框架算法效率分析框架本节将概要地描述一个分析算法效率的一般性框架。时间效率指出算法运行得有多快；空间效率关心算法需要的额外空间。目前，随着计算机硬件技术的飞速发展，空间效率已不是关心重点。因此，我们主要关心的是时间效率。输入规模的度量：（问题规模）一个显而易见的事实：几乎所有的算法，对于更大规模输入都需要运行更长

2、的时间（即算法耗费的时间随着输入规模的增大而增加）。例如：1.更大的数组排序需要花费更多的运行时间；2.更大的矩阵相乘需要花费更多的运算时间。因此，采用一个以算法输入规模n为参数的函数，来研究算法效率就是非常合乎逻辑的。输入规模的选择问题：在大多数情况下，选择这样一个参数是非常直接的。例如，对于排序、查找以及其他大多数与列表相关的问题来讲，这个参数就是列表长度；对于n次多项式求值问题，这个参数是多项式次数或者系数个数。5输入规模的选择当然，有些情况下，怎样选择输入规模参数是有差别的。例如计算两个n阶矩阵的乘积，有两种度量输入规模的方法：第一种方法：选择矩阵的阶n；

3、第二种方法：选择参与乘法运算的所有元素个数。第二种方法更具一般性，适用于非方阵。对于选择不同的输入规模，其算法效率在含义上有所差别。选择输入规模参数的合适量度，会受到算法操作细节的影响。例如：对于一个检查文字拼写的算法，如果算法要求对每个字符都要检查，那么应该用字符数作为输入规模度量；如果算法操作的是单词，那么选择单词数作为输入规模的度量。若算法与数字特性（数字的大小）相关，那么在度量它的输入规模时，计算机科学家倾向于选择数字的二进制位数作为输入规模的度量。6时间效率的度量运行时间的度量：接下来考虑运行时间的度量问题。我们为何不选择时间的标准度量单位（秒、毫秒等）

4、来度量算法的运行时间呢？其理由如下：1.它依赖于特定计算机的运行速度；2.它依赖于实现算法的代码质量；（程序员编程的水平问题）3.它依赖于编译器的好坏；（编译成机器码的质量，即指令条数）4.它还依赖于一些其他问题如操作系统的调度策略等。鉴于此，希望找到一个不依赖于上述因素的时间度量。问：是否统计算法的每步操作执行次数来作为算法的时间效率度量呢？答：无此必要且较困难。一个算法中有许多操作，决定算法时间效率的是那些很耗费时间的操作步，因此只需关心这些操作即可评价一个算法时间效率，这些最关键的操作步称为基本操作，它们对算法执行时间的占用最大（基本操作即算法中最费时的操作

5、）。所以，用基本操作执行次数来作为时间效率的度量。7基本操作的选取基本操作的选取例：大多数排序算法是通过比较排序元素（键）来进行工作，因此它的基本操作应选为键的比较操作，即算法中键的比较次数。矩阵乘法（或多项式运算）需完成两种操作：乘法和加法。对多数机器而言，乘法比加法更耗费时间，所以选取乘法为基本操作。在定义了算法的输入规模n和基本操作后，我们就可以建立起一个算法时间效率的分析框架：对规模为n的算法，通过统计其基本操作的执行次数来度量算法的时间效率。（时间耗费T为输入规模n的函数）分析框架的应用：设t为算法的一个基本操作在特定机器上的执行时间，C(n)为该算法需

6、执行的基本操作数。用下式来估计该算法在该机器上的运行时间：忽略了非基本操作执行时间问：为什么用约等于符号？8分析框架的应用例分析框架的应用例：根据上式，我们可以回答以下问题：1若某算法运行在一台比现在机器快10倍的机器上，此算法运行多快？答：10倍。（t增加10倍，C(n)不变）2设，若输入规模翻倍，该算法运行时间如何变化？（n不是太小如n=100）不考虑每个操作步在机器上具体的执行时间t，则时间耗费即为：时间耗费即为基本操作数，为输入规模n的函数。n的一次、二次函数分别称线性、二次增长率。2n称指数增长率。9增长次数（增长率）增长次数（增长率）基本操作数（时间耗

7、费）是输入规模n的函数，记为T(n)。T(n)随着n次数的增加而增加。函数值T(n)增加快慢，决定于这个增长函数特性；也就是说，线性增长函数的函数值增加较慢，二次增长函数增加较快，指数增长函数最快。因此，我们最关心的就是函数的增长率，它决定了算法的时间耗费（效率）。若输入规模n很小，无论是高效的算法还是低效的算法，时间耗费差距不明显，所以算法分析针对大规模输入。增长函数表：对于算法分析具有重要意义的函数值（近似值）阶乘指数三次二次n-log-n线性对数规模101810122.0×10710620106101510101.7×1061051710510121081.

8、3×105