《第2章 算法效率分析基础》由会员分享，可在线阅读，更多相关《第2章 算法效率分析基础（44页珍藏版）》请在金锄头文库上搜索。
1、算法设计与分析计算机与信息学院,2,使用教材,使用教材,作者：（美）Anany Levitin 译者：潘彦出版社：清华大学丛书名：国外经典教材 计算机 科学与技术,第 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,增长次数（增长率）,增长次数（增长率）基本操作数（时间耗费）是输入规模 n 的函数
7、，记为T(n) 。T(n) 随着 n 次数的增加而增加。函数值T(n) 增加快慢，决定于这个增长函数特性；也就是说，线性增长函数的函数值增加较慢，二次增长函数增加较快，指数增长函数最快。因此，我们最关心的就是函数的增长率，它决定了算法的时间耗费（效率）。若输入规模 n 很小，无论是高效的算法还是低效的算法，时间耗费差距不明显，所以算法分析针对大规模输入。,增长函数表：对于算法分析具有重要意义的函数值（近似值）,10,算法效率算例,算法的最优、最差、平均效率前述已知，我们用输入规模 n 的函数 T(n) 来度量算法的效率。若T(n) 随n 增长快，则算法效率较差；若T(n) 随 n 增长较慢，则
8、算法效率更好。这里，没考虑算法效率与特定输入的关系。诸多算法的效率不仅与规模有关，且与特定的输入有关。下面以顺序查找算法为例：-【 名称 】顺序查找【 要求 】在列表中查找一次给定项（查找键），该列表有 n 个元素。【 算法 】从列表头开始，逐个比较列表中元素，直到发现匹配查找键的 元素或者到达列表尾为止（没找到）。【 分析 】1. 很明显，该算法的执行效率与查找键在列表中的位置有密切关系。2. 若查找键位于表头（第一个元素），该算法只比较一次。最优效率3. 若查找键位于表尾（最末元素）或不存在，该算法将比较 n 次。最差4. 若查找键位于表中间，该算法比较次数不固定。平均效率-通过上述例子，
9、引入最佳、最差和平均效率的概念。,11,最优、最差效率,1 最差效率：（最为关注）当输入规模为 n 时，算法在最坏情况下的效率。此时，相对于其他规模为 n 的输入，该算法运行时间最长（最慢）。最差效率的确定：原理上讲，首先对算法作一个分析，看看在规模 n 的所有可能输入中，那种输入会导致基本操作数 C(n) 达到最大值，计算这个最差值 Cworse(n)。后面讲到，通过确定算法运行时间的上界，分析最坏情况为算法效率提供一个非常重要的信息。也即，对于任何规模 n的实例来讲，它保证算法运行时间不会超过最坏输入情况下的运行时间 Cworse(n)。（最差效率分析的价值） 顺序查找： Cworse(n
10、) = n2 最优效率：当输入规模为 n 时，算法在最优情况下的效率。此时，相对于其他规模为 n 的输入，该算法运行时间最短（最快）。顺序查找： Cbest (n) = 1最优效率分析的价值：远不如最差效率分析重要，因不能指望每次输入都是最优输入。但它对算法的的选择有指导意义， 例如：某算法在有序列表情况下效率很高，对于基本有序的输入数据，该算法可以获得接近最优输入的效率，实际中可考虑选择该算法。重要的是，如果一个算法的最优效率都不能满足实际需要，可立即抛弃该算法。,12,平均效率,3 平均效率无论是最优还是最差效率，都不能提供这样一种必要信息：在随机输入情况下，该算法具有怎样的行为（时间耗费
11、）。为此，引入平均效率 。平均效率分析要比最差和最优效率分析困难很多。以后讨论平均效率时都引用其已知的推导结果。对推导有兴趣的同学，请查阅有关书籍。平均效率分析的价值：有许多重要算法的平均效率比它们过于悲观的最差效率要好很多。所以如果没有平均效率分析的话，我们会错失不少重要的算法。显然，我们不能通过求最优和最差效率平均值的方法来求平均效率。平均效率分析的直接法：1 将输入分为几种类型（可能的话），目的是使得对于同种输入类型的 实例，具有相同的基本操作数。2 得到或者假设各类输入的概率分布，以推导出基本操作的平均次数。 但各类输入的概率模型往往又难以验证，虽然它可能很合理。,13,顺序查找算法的
12、平均时间效率,顺序查找算法的平均时间效率：假设：(1) 成功查找的概率是 p (0p1)，查找不成功的概率是 1- p；(2) 对任意第 i 次查找，第一次成功匹配（查找成功）发生在列表第 i 个位置的概率相同，即查找键位于列表任一位置上的概率相同 1/n 。基于假设，在列表任一位置上查找成功的概率为 p(1/n)（甚至可进一步假设p=0.5）。若查找成功的位置为 i ，算法做的比较次数（基本操作）为i 次，考虑成功查找概率，比较次数为 p(i/n)；若查找不成功，算法做的比较次数为 n（列表全部查找一遍），考虑不成功查找概率，比较次数则为 n(1-p)。因此，算法平均效率：,统计平均,14,
13、摊销效率,4 摊销效率它并不适合于算法的单次运行，而应用于算法对同样数据的多次运行。我们知道，在有些情况下单次运行的时间代价可能比较昂贵，但 n 次运行的总时间花费明显低于单次运行的最差效率乘以 n ，因此我们把最差效率的高成本摊到各次运行中去，即摊销效率。该做法与商业中把固定资产成本按其使用年限摊销到整个序列（各年）中的做法一致。通常，具备这种运行特性的算法是在一定程度上的具有“智能”的算法，通过“学习”获得“知识”累积，再运用知识库中的有关知识对算法下次如何执行提供指导，从而提高以后运行的效率。一个例子：汉字拼音输入法中的动态词频调整算法。它统计不同用户对某些字词的使用率（学习积累过程），
14、来动态调整这些字词下次出现的先后顺序，高频先现，达到减少用户翻阅时间的目的，提高了该算法的执行效率。-后续章节中，除非专门说明，都将最差情况下时间耗费的极限作为算法的时间耗费，称时间复杂性或时间效率。求解过程称为时间渐进分析。,15,渐进符号,渐进符号和基本效率类型上节指出，效率分析主要关心的是一个算法的基本操作数随问题规模的增长率（增长次数），即问题规模 n 变大情况下，该算法的基本操作数增长的快慢（它是规模 n 的函数增长函数）。为了对增长函数作出比较和归类，通常使用三种符号：O,(theta). 下面就这些符号先作一个非正式介绍（便于理解）。T(n) 和 g(n) ：定义在自然数集合上的
15、任意非负函数（n取自然数）；T(n) ：算法的运行时间函数（常用基本操作数增长函数 C(n) 表示）；g(n) ：与增长函数作比较的函数。非正式介绍O(g(n) ：增长次数小于等于g(n)（包括其常数倍，n 趋于无穷大）的 函数集合。即 g(n) 是增长函数集的上界。例如：,16,上界符号,(g(n) ：增长次数大于等于g(n)（包括其常数倍，n 趋于无穷大）的 函数集合。即 g(n) 是增长函数集的下界。例如：(g(n) ：增长次数等于g(n)（包括其常数倍，n 趋于无穷大）的函数 集合。即 g(n) 与增长函数集同阶（相同的增长率）。例如：上界符号 O （最常用）定义：把函数T(n)包含在O(g(n)中，记为T(n)O(g(n)；它成立的条件是：对于足够大的 n，T(n) 的上界由g(n)的常数倍决定。即存在正数c 和非负整数 n0，使得下式成立：,
