算法效率分析基础.ppt

《算法效率分析基础.ppt》由会员分享，可在线阅读，更多相关《算法效率分析基础.ppt（47页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、算法设计与分析算法设计与分析计算机与信息学院计算机与信息学院计算机与信息学院计算机与信息学院 2使用教材 使用教材使用教材使用教材使用教材作者：（美）作者：（美）Anany Levitin 译者：潘彦译者：潘彦出版社：清华大学出版社：清华大学丛书名：国外经典教材丛书名：国外经典教材 计算机计算机 科学与技术科学与技术第第 2 2章章 算法效率分析基础算法效率分析基础 算法效率分析框架算法效率分析框架算法效率分析框架算法效率分析框架 渐进符号和基本效率类型渐进符号和基本效率类型渐进符号和基本效率类型渐进符号和基本效率类型 非递归算法效率分析非递归算法效率分析非递归算法效率分析非递归算法效率分析

2、递归算法效率分析递归算法效率分析递归算法效率分析递归算法效率分析 4算法效率分析框架 算法效率分析框架算法效率分析框架算法效率分析框架算法效率分析框架本节将概要地描述一个分析算法效率的一般性框架。本节将概要地描述一个分析算法效率的一般性框架。本节将概要地描述一个分析算法效率的一般性框架。本节将概要地描述一个分析算法效率的一般性框架。时间效率时间效率时间效率时间效率指出算法运行得有多快；指出算法运行得有多快；指出算法运行得有多快；指出算法运行得有多快；空间效率空间效率空间效率空间效率关心算法需要的额外空间。关心算法需要的额外空间。关心算法需要的额外空间。关心算法需要的额外空间。目前，随着计算机硬

3、件技术的飞速发展，空间效率已不是关心重点。目前，随着计算机硬件技术的飞速发展，空间效率已不是关心重点。目前，随着计算机硬件技术的飞速发展，空间效率已不是关心重点。目前，随着计算机硬件技术的飞速发展，空间效率已不是关心重点。因此，我们主要关心的是时间效率。因此，我们主要关心的是时间效率。因此，我们主要关心的是时间效率。因此，我们主要关心的是时间效率。vv输入规模的度量：（问题规模）输入规模的度量：（问题规模）输入规模的度量：（问题规模）输入规模的度量：（问题规模）一个显而易见的事实：几乎所有的算法，对于更大规模输入都需要运行一个显而易见的事实：几乎所有的算法，对于更大规模输入都需要运行一个显而易

4、见的事实：几乎所有的算法，对于更大规模输入都需要运行一个显而易见的事实：几乎所有的算法，对于更大规模输入都需要运行更长的时间（即算法耗费的时间随着输入规模的增大而增加）更长的时间（即算法耗费的时间随着输入规模的增大而增加）更长的时间（即算法耗费的时间随着输入规模的增大而增加）更长的时间（即算法耗费的时间随着输入规模的增大而增加）。例如：。例如：。例如：。例如：1.1.更大的数组排序需要花费更多的运行时间；更大的数组排序需要花费更多的运行时间；更大的数组排序需要花费更多的运行时间；更大的数组排序需要花费更多的运行时间；2.2.更大的矩阵相乘需要花费更多的运算时间。更大的矩阵相乘需要花费更多的运算

5、时间。更大的矩阵相乘需要花费更多的运算时间。更大的矩阵相乘需要花费更多的运算时间。因此，采用一个以算法因此，采用一个以算法因此，采用一个以算法因此，采用一个以算法输入规模输入规模输入规模输入规模 n n 为参数的函数为参数的函数为参数的函数为参数的函数，来研究算法效率就是，来研究算法效率就是，来研究算法效率就是，来研究算法效率就是非常合乎逻辑的。非常合乎逻辑的。非常合乎逻辑的。非常合乎逻辑的。w w输入规模的选择问题输入规模的选择问题输入规模的选择问题输入规模的选择问题：在大多数情况下，选择这样一个参数是非常直接的。例如，对于排序、在大多数情况下，选择这样一个参数是非常直接的。例如，对于排序、

6、在大多数情况下，选择这样一个参数是非常直接的。例如，对于排序、在大多数情况下，选择这样一个参数是非常直接的。例如，对于排序、查找以及其他大多数与列表相关的问题来讲，这个参数就是列表长度；查找以及其他大多数与列表相关的问题来讲，这个参数就是列表长度；查找以及其他大多数与列表相关的问题来讲，这个参数就是列表长度；查找以及其他大多数与列表相关的问题来讲，这个参数就是列表长度；对于对于对于对于 n n 次多项式求值问题，这个参数是多项式次数或者系数个数。次多项式求值问题，这个参数是多项式次数或者系数个数。次多项式求值问题，这个参数是多项式次数或者系数个数。次多项式求值问题，这个参数是多项式次数或者系数

7、个数。5输入规模的选择当然，有些情况下，怎样选择输入规模参数是有差别的。例如计算两个当然，有些情况下，怎样选择输入规模参数是有差别的。例如计算两个当然，有些情况下，怎样选择输入规模参数是有差别的。例如计算两个当然，有些情况下，怎样选择输入规模参数是有差别的。例如计算两个n n 阶矩阵的乘积，有两种度量输入规模的方法：阶矩阵的乘积，有两种度量输入规模的方法：阶矩阵的乘积，有两种度量输入规模的方法：阶矩阵的乘积，有两种度量输入规模的方法：第一种方法：选择矩阵的阶第一种方法：选择矩阵的阶第一种方法：选择矩阵的阶第一种方法：选择矩阵的阶 n n；第二种方法：选择参与乘法运算的所有元素个数。第二种方法：

8、选择参与乘法运算的所有元素个数。第二种方法：选择参与乘法运算的所有元素个数。第二种方法：选择参与乘法运算的所有元素个数。第二种方法更具一般性，适用于非方阵。第二种方法更具一般性，适用于非方阵。第二种方法更具一般性，适用于非方阵。第二种方法更具一般性，适用于非方阵。对于选择不同的输入规模，其算法效率在含义上有所差别。对于选择不同的输入规模，其算法效率在含义上有所差别。对于选择不同的输入规模，其算法效率在含义上有所差别。对于选择不同的输入规模，其算法效率在含义上有所差别。选择输入规模参数的合适量度，会受到算法操作细节的影响。例如：选择输入规模参数的合适量度，会受到算法操作细节的影响。例如：选择输入

9、规模参数的合适量度，会受到算法操作细节的影响。例如：选择输入规模参数的合适量度，会受到算法操作细节的影响。例如：对于一个检查文字拼写的算法，如果算法要求对每个字符都要检查，对于一个检查文字拼写的算法，如果算法要求对每个字符都要检查，对于一个检查文字拼写的算法，如果算法要求对每个字符都要检查，对于一个检查文字拼写的算法，如果算法要求对每个字符都要检查，那么应该用字符数作为输入规模度量；如果算法操作的是单词，那么那么应该用字符数作为输入规模度量；如果算法操作的是单词，那么那么应该用字符数作为输入规模度量；如果算法操作的是单词，那么那么应该用字符数作为输入规模度量；如果算法操作的是单词，那么选择单词

10、数作为输入规模的度量。选择单词数作为输入规模的度量。选择单词数作为输入规模的度量。选择单词数作为输入规模的度量。若算法与数字特性（数字的大小）相关，那么在度量它的输入规模时，若算法与数字特性（数字的大小）相关，那么在度量它的输入规模时，若算法与数字特性（数字的大小）相关，那么在度量它的输入规模时，若算法与数字特性（数字的大小）相关，那么在度量它的输入规模时，计算机科学家倾向于选择数字的二进制位数作为输入规模的度量。计算机科学家倾向于选择数字的二进制位数作为输入规模的度量。计算机科学家倾向于选择数字的二进制位数作为输入规模的度量。计算机科学家倾向于选择数字的二进制位数作为输入规模的度量。6时间效

11、率的度量vv运行时间的度量：运行时间的度量：运行时间的度量：运行时间的度量：接下来考虑运行时间的度量问题。我们为何不选择时间的标准度量单位接下来考虑运行时间的度量问题。我们为何不选择时间的标准度量单位接下来考虑运行时间的度量问题。我们为何不选择时间的标准度量单位接下来考虑运行时间的度量问题。我们为何不选择时间的标准度量单位（秒、毫秒等）来度量算法的运行时间呢？其（秒、毫秒等）来度量算法的运行时间呢？其（秒、毫秒等）来度量算法的运行时间呢？其（秒、毫秒等）来度量算法的运行时间呢？其理由理由理由理由如下：如下：如下：如下：1.1.它依赖于特定计算机的运行速度；它依赖于特定计算机的运行速度；它依赖于

12、特定计算机的运行速度；它依赖于特定计算机的运行速度；2.2.它依赖于实现算法的代码质量；（程序员编程的水平问题）它依赖于实现算法的代码质量；（程序员编程的水平问题）它依赖于实现算法的代码质量；（程序员编程的水平问题）它依赖于实现算法的代码质量；（程序员编程的水平问题）3.3.它依赖于编译器的好坏；（编译成机器码的质量，即指令条数）它依赖于编译器的好坏；（编译成机器码的质量，即指令条数）它依赖于编译器的好坏；（编译成机器码的质量，即指令条数）它依赖于编译器的好坏；（编译成机器码的质量，即指令条数）4.4.它还依赖于一些其他问题如操作系统的调度策略等。它还依赖于一些其他问题如操作系统的调度策略等。

13、它还依赖于一些其他问题如操作系统的调度策略等。它还依赖于一些其他问题如操作系统的调度策略等。鉴于此，希望找到一个不依赖于上述因素的时间度量。鉴于此，希望找到一个不依赖于上述因素的时间度量。鉴于此，希望找到一个不依赖于上述因素的时间度量。鉴于此，希望找到一个不依赖于上述因素的时间度量。问：问：问：问：是否统计算法的是否统计算法的是否统计算法的是否统计算法的每步操作执行次数每步操作执行次数每步操作执行次数每步操作执行次数来作为算法的时间效率度量呢？来作为算法的时间效率度量呢？来作为算法的时间效率度量呢？来作为算法的时间效率度量呢？答：答：答：答：无此必要且较困难。一个算法中有许多操作，决定算法时间

14、效率的无此必要且较困难。一个算法中有许多操作，决定算法时间效率的无此必要且较困难。一个算法中有许多操作，决定算法时间效率的无此必要且较困难。一个算法中有许多操作，决定算法时间效率的是那些很耗费时间的操作步，因此只需关心这些操作即可评价一个算法是那些很耗费时间的操作步，因此只需关心这些操作即可评价一个算法是那些很耗费时间的操作步，因此只需关心这些操作即可评价一个算法是那些很耗费时间的操作步，因此只需关心这些操作即可评价一个算法时间效率，这些最关键的操作步称为时间效率，这些最关键的操作步称为时间效率，这些最关键的操作步称为时间效率，这些最关键的操作步称为基本操作基本操作基本操作基本操作，它们对算法

15、执行时间的，它们对算法执行时间的，它们对算法执行时间的，它们对算法执行时间的占用最大（基本操作即算法中最费时的操作）。所以，占用最大（基本操作即算法中最费时的操作）。所以，占用最大（基本操作即算法中最费时的操作）。所以，占用最大（基本操作即算法中最费时的操作）。所以，用基本操作执行用基本操作执行用基本操作执行用基本操作执行次数来作为时间效率的度量次数来作为时间效率的度量次数来作为时间效率的度量次数来作为时间效率的度量。7基本操作的选取w w基本操作的选取例基本操作的选取例基本操作的选取例基本操作的选取例：大多数排序算法是通过比较排序元素（键）来进行工作，因此它的基本大多数排序算法是通过比较排序

16、元素（键）来进行工作，因此它的基本大多数排序算法是通过比较排序元素（键）来进行工作，因此它的基本大多数排序算法是通过比较排序元素（键）来进行工作，因此它的基本操作应选为键的操作应选为键的操作应选为键的操作应选为键的比较比较比较比较操作操作操作操作，即算法中键的比较次数。，即算法中键的比较次数。，即算法中键的比较次数。，即算法中键的比较次数。矩阵乘法（或多项式运算）需完成两种操作：乘法和加法。对多数机器矩阵乘法（或多项式运算）需完成两种操作：乘法和加法。对多数机器矩阵乘法（或多项式运算）需完成两种操作：乘法和加法。对多数机器矩阵乘法（或多项式运算）需完成两种操作：乘法和加法。对多数机器而言，乘法

17、比加法更耗费时间，所以选取乘法为基本操作。而言，乘法比加法更耗费时间，所以选取乘法为基本操作。而言，乘法比加法更耗费时间，所以选取乘法为基本操作。而言，乘法比加法更耗费时间，所以选取乘法为基本操作。在定义了算法的输入规模在定义了算法的输入规模在定义了算法的输入规模在定义了算法的输入规模 n n 和基本操作后，我们就可以建立起一个算法和基本操作后，我们就可以建立起一个算法和基本操作后，我们就可以建立起一个算法和基本操作后，我们就可以建立起一个算法w w时间效率的分析框架时间效率的分析框架时间效率的分析框架时间效率的分析框架：对规模为对规模为对规模为对规模为 n n 的算法，通过统计其基本操作的的

18、算法，通过统计其基本操作的的算法，通过统计其基本操作的的算法，通过统计其基本操作的执行次数来度量算法的时间效率执行次数来度量算法的时间效率执行次数来度量算法的时间效率执行次数来度量算法的时间效率。（时间耗费。（时间耗费。（时间耗费。（时间耗费 T T 为输入规模为输入规模为输入规模为输入规模 n n 的函数）的函数）的函数）的函数）w w分析框架的应用分析框架的应用分析框架的应用分析框架的应用：设设设设 t t 为算法的一个基本操作在特定机器上的执行时间，为算法的一个基本操作在特定机器上的执行时间，为算法的一个基本操作在特定机器上的执行时间，为算法的一个基本操作在特定机器上的执行时间，C(n)

19、C(n)为该算法需为该算法需为该算法需为该算法需执行的基本操作数。用下式来估计该算法在该机器上的运行时间：执行的基本操作数。用下式来估计该算法在该机器上的运行时间：执行的基本操作数。用下式来估计该算法在该机器上的运行时间：执行的基本操作数。用下式来估计该算法在该机器上的运行时间：忽略了非基本忽略了非基本操作执行时间操作执行时间问：问：问：问：为什么用约等于符号？为什么用约等于符号？8分析框架的应用例w w分析框架的应用例：分析框架的应用例：分析框架的应用例：分析框架的应用例：根据上式，我们可以回答以下问题：根据上式，我们可以回答以下问题：根据上式，我们可以回答以下问题：根据上式，我们可以回答以

20、下问题：1 1 若某算法运行在一台比现在机器快若某算法运行在一台比现在机器快若某算法运行在一台比现在机器快若某算法运行在一台比现在机器快1010倍的机器上，此算法运行多快？倍的机器上，此算法运行多快？倍的机器上，此算法运行多快？倍的机器上，此算法运行多快？答：答：答：答：1010倍。（倍。（倍。（倍。（t t 增加增加增加增加1010倍，倍，倍，倍，C(n)C(n)不变）不变）不变）不变）2 2 设设设设 ，若输入规模翻倍，该算法运行时间如何变化？，若输入规模翻倍，该算法运行时间如何变化？，若输入规模翻倍，该算法运行时间如何变化？，若输入规模翻倍，该算法运行时间如何变化？（n 不是太小如不是太

21、小如 n=100）不考虑每个操作步在机器上具体的执行时间不考虑每个操作步在机器上具体的执行时间 t，则时间耗费即为：，则时间耗费即为：时间耗费即为基本操作数，为输入规模时间耗费即为基本操作数，为输入规模n的函数。的函数。n的一次、二次函数分别称线性、二次增长率。的一次、二次函数分别称线性、二次增长率。2n 称指数增长率。称指数增长率。9增长次数（增长率）vv增长次数（增长率）增长次数（增长率）增长次数（增长率）增长次数（增长率）基本操作数（时间耗费）是输入规模基本操作数（时间耗费）是输入规模基本操作数（时间耗费）是输入规模基本操作数（时间耗费）是输入规模 n n 的函数，记为的函数，记为的函数

22、，记为的函数，记为T(n)T(n)。T(n)T(n)随着随着随着随着 n n 次数的增加而增加。函数值次数的增加而增加。函数值次数的增加而增加。函数值次数的增加而增加。函数值T(n)T(n)增加快慢，决定于这个增长函数特性；增加快慢，决定于这个增长函数特性；增加快慢，决定于这个增长函数特性；增加快慢，决定于这个增长函数特性；也就是说，线性增长函数的函数值增加较慢，二次增长函数增加较快，也就是说，线性增长函数的函数值增加较慢，二次增长函数增加较快，也就是说，线性增长函数的函数值增加较慢，二次增长函数增加较快，也就是说，线性增长函数的函数值增加较慢，二次增长函数增加较快，指数增长函数最快。因此，我

23、们最关心的就是函数的增长率，它决定了指数增长函数最快。因此，我们最关心的就是函数的增长率，它决定了指数增长函数最快。因此，我们最关心的就是函数的增长率，它决定了指数增长函数最快。因此，我们最关心的就是函数的增长率，它决定了算法的时间耗费（效率）。若输入规模算法的时间耗费（效率）。若输入规模算法的时间耗费（效率）。若输入规模算法的时间耗费（效率）。若输入规模 n n 很小，无论是高效的算法还是很小，无论是高效的算法还是很小，无论是高效的算法还是很小，无论是高效的算法还是低效的算法，时间耗费差距不明显，所以算法分析针对大规模输入。低效的算法，时间耗费差距不明显，所以算法分析针对大规模输入。低效的算

24、法，时间耗费差距不明显，所以算法分析针对大规模输入。低效的算法，时间耗费差距不明显，所以算法分析针对大规模输入。增长函数表：对于算法分析具有重要意义的函数值（近似值）增长函数表：对于算法分析具有重要意义的函数值（近似值）阶乘阶乘阶乘阶乘指数指数指数指数三次三次三次三次二次二次二次二次n-log-nn-log-n线性线性线性线性对数对数对数对数规模规模规模规模101010101818181810101010121212122.0102.0102.0102.0107 7 7 7101010106 6 6 620202020101010106 6 6 610101010151515151010101

25、0101010101.7101.7101.7101.7106 6 6 6101010105 5 5 517171717101010105 5 5 51010101012121212101010108 8 8 81.3101.3101.3101.3105 5 5 5101010104 4 4 413131313101010104 4 4 4101010109 9 9 9101010106 6 6 61.0101.0101.0101.0104 4 4 4101010103 3 3 310101010101010103 3 3 39.3109.3109.3109.3101571571571571.3

26、101.3101.3101.31030303030101010106 6 6 6101010104 4 4 46.6106.6106.6106.6102 2 2 2101010102 2 2 26.66.66.66.6101010102 2 2 23.6103.6103.6103.6106 6 6 62 2 2 210101010101010103 3 3 3101010102 2 2 23.3103.3103.3103.3101 1 1 1101010101 1 1 13.33.33.33.3101010101 1 1 1n!n!2 2n nn n3 3n n2 2nlognlog2 2n

27、nn n1 1loglog2 2n nn n一个需要指数级操作次数的算法只能用来解决规模非常小的问题。一个需要指数级操作次数的算法只能用来解决规模非常小的问题。10算法效率算例vv算法的最优、最差、平均效率算法的最优、最差、平均效率算法的最优、最差、平均效率算法的最优、最差、平均效率前述已知，我们用输入规模前述已知，我们用输入规模前述已知，我们用输入规模前述已知，我们用输入规模 n n 的函数的函数的函数的函数 T(n)T(n)来度量算法的效率。若来度量算法的效率。若来度量算法的效率。若来度量算法的效率。若T(n)T(n)随随随随n n 增长快，则算法效率较差；若增长快，则算法效率较差；若增长

28、快，则算法效率较差；若增长快，则算法效率较差；若T(n)T(n)随随随随 n n 增长较慢，则算法效率更好。增长较慢，则算法效率更好。增长较慢，则算法效率更好。增长较慢，则算法效率更好。这里，没考虑算法效率与特定输入的关系。诸多算法的效率不仅与规模这里，没考虑算法效率与特定输入的关系。诸多算法的效率不仅与规模这里，没考虑算法效率与特定输入的关系。诸多算法的效率不仅与规模这里，没考虑算法效率与特定输入的关系。诸多算法的效率不仅与规模有关，且与特定的输入有关。下面以顺序查找算法为例：有关，且与特定的输入有关。下面以顺序查找算法为例：有关，且与特定的输入有关。下面以顺序查找算法为例：有关，且与特定的

29、输入有关。下面以顺序查找算法为例：-【名称名称名称名称 】顺序查找顺序查找顺序查找顺序查找【要求要求要求要求 】在列表中查找一次在列表中查找一次在列表中查找一次在列表中查找一次给定项给定项给定项给定项（查找键），该列表有（查找键），该列表有（查找键），该列表有（查找键），该列表有 n n 个元素。个元素。个元素。个元素。【算法算法算法算法 】从列表头开始，逐个从列表头开始，逐个从列表头开始，逐个从列表头开始，逐个比较比较比较比较列表中元素，直到发现匹配查找键的列表中元素，直到发现匹配查找键的列表中元素，直到发现匹配查找键的列表中元素，直到发现匹配查找键的 元素或者到达列表尾为止（没找到）。元素

30、或者到达列表尾为止（没找到）。元素或者到达列表尾为止（没找到）。元素或者到达列表尾为止（没找到）。【分析分析分析分析 】1.1.很明显，该算法的执行效率与查找键在列表中的位置有密切关系。很明显，该算法的执行效率与查找键在列表中的位置有密切关系。很明显，该算法的执行效率与查找键在列表中的位置有密切关系。很明显，该算法的执行效率与查找键在列表中的位置有密切关系。2.2.若查找键位于表头（第一个元素），该算法只若查找键位于表头（第一个元素），该算法只若查找键位于表头（第一个元素），该算法只若查找键位于表头（第一个元素），该算法只比较比较比较比较一次。一次。一次。一次。最优效率最优效率最优效率最优效率

31、3.3.若查找键位于表尾（最末元素）或不存在，该算法将若查找键位于表尾（最末元素）或不存在，该算法将若查找键位于表尾（最末元素）或不存在，该算法将若查找键位于表尾（最末元素）或不存在，该算法将比较比较比较比较 n n 次。次。次。次。最差最差最差最差4.4.若查找键位于表中间，该算法若查找键位于表中间，该算法若查找键位于表中间，该算法若查找键位于表中间，该算法比较比较比较比较次数不固定。次数不固定。次数不固定。次数不固定。平均效率平均效率平均效率平均效率-通过上述例子，引入最佳、最差和平均效率的概念。通过上述例子，引入最佳、最差和平均效率的概念。通过上述例子，引入最佳、最差和平均效率的概念。通

32、过上述例子，引入最佳、最差和平均效率的概念。11最优、最差效率1 1 1 1 最差效率最差效率最差效率最差效率：（最为关注）（最为关注）（最为关注）（最为关注）当输入规模为当输入规模为当输入规模为当输入规模为 n n 时，算法在最坏情况下的效率。此时，相对于其他规模时，算法在最坏情况下的效率。此时，相对于其他规模时，算法在最坏情况下的效率。此时，相对于其他规模时，算法在最坏情况下的效率。此时，相对于其他规模为为为为 n n 的输入，该算法运行时间最长（最慢）。的输入，该算法运行时间最长（最慢）。的输入，该算法运行时间最长（最慢）。的输入，该算法运行时间最长（最慢）。最差效率的确定最差效率的确定

33、最差效率的确定最差效率的确定：原理上讲，首先对算法作一个分析，看看在规模：原理上讲，首先对算法作一个分析，看看在规模：原理上讲，首先对算法作一个分析，看看在规模：原理上讲，首先对算法作一个分析，看看在规模 n n 的的的的所有可能输入中，那种输入会导致基本操作数所有可能输入中，那种输入会导致基本操作数所有可能输入中，那种输入会导致基本操作数所有可能输入中，那种输入会导致基本操作数 C(n)C(n)达到最大值，计算达到最大值，计算达到最大值，计算达到最大值，计算这个最差值这个最差值这个最差值这个最差值 C Cworseworse(n)(n)。后面讲到，通过确定。后面讲到，通过确定。后面讲到，通过

34、确定。后面讲到，通过确定算法运行时间的上界算法运行时间的上界算法运行时间的上界算法运行时间的上界，分析，分析，分析，分析最坏情况为算法效率提供一个非常重要的信息。也即，对于任何规模最坏情况为算法效率提供一个非常重要的信息。也即，对于任何规模最坏情况为算法效率提供一个非常重要的信息。也即，对于任何规模最坏情况为算法效率提供一个非常重要的信息。也即，对于任何规模 n n的实例来讲，的实例来讲，的实例来讲，的实例来讲，它保证算法运行时间不会超过最坏输入情况下的运行时间它保证算法运行时间不会超过最坏输入情况下的运行时间它保证算法运行时间不会超过最坏输入情况下的运行时间它保证算法运行时间不会超过最坏输入

35、情况下的运行时间 C Cworseworse(n)(n)。（。（。（。（最差效率分析的价值最差效率分析的价值最差效率分析的价值最差效率分析的价值）顺序查找：顺序查找：顺序查找：顺序查找：C Cworseworse(n)(n)=n n2 2 2 2 最优效率：最优效率：最优效率：最优效率：当输入规模为当输入规模为当输入规模为当输入规模为 n n 时，算法在最优情况下的效率。此时，相对于其他规模时，算法在最优情况下的效率。此时，相对于其他规模时，算法在最优情况下的效率。此时，相对于其他规模时，算法在最优情况下的效率。此时，相对于其他规模为为为为 n n 的输入，该算法运行时间最短（最快）。顺序查找

36、：的输入，该算法运行时间最短（最快）。顺序查找：的输入，该算法运行时间最短（最快）。顺序查找：的输入，该算法运行时间最短（最快）。顺序查找：C Cbest best(n)(n)=1 1最优效率分析的价值最优效率分析的价值最优效率分析的价值最优效率分析的价值：远不如最差效率分析重要，因不能指望每次输入：远不如最差效率分析重要，因不能指望每次输入：远不如最差效率分析重要，因不能指望每次输入：远不如最差效率分析重要，因不能指望每次输入都是最优输入。但它对都是最优输入。但它对都是最优输入。但它对都是最优输入。但它对算法的的选择算法的的选择算法的的选择算法的的选择有指导意义，有指导意义，有指导意义，有指

37、导意义，例如：某算法在有序例如：某算法在有序例如：某算法在有序例如：某算法在有序列表情况下效率很高，对于基本有序的输入数据，该算法可以获得接近列表情况下效率很高，对于基本有序的输入数据，该算法可以获得接近列表情况下效率很高，对于基本有序的输入数据，该算法可以获得接近列表情况下效率很高，对于基本有序的输入数据，该算法可以获得接近最优输入的效率，实际中可考虑选择该算法。重要的是，最优输入的效率，实际中可考虑选择该算法。重要的是，最优输入的效率，实际中可考虑选择该算法。重要的是，最优输入的效率，实际中可考虑选择该算法。重要的是，如果一个算法如果一个算法如果一个算法如果一个算法的最优效率都不能满足实际

38、需要，可立即抛弃该算法的最优效率都不能满足实际需要，可立即抛弃该算法的最优效率都不能满足实际需要，可立即抛弃该算法的最优效率都不能满足实际需要，可立即抛弃该算法。12平均效率3 3 3 3 平均效率平均效率平均效率平均效率无论是最优还是最差效率，都不能提供这样一种必要信息：无论是最优还是最差效率，都不能提供这样一种必要信息：无论是最优还是最差效率，都不能提供这样一种必要信息：无论是最优还是最差效率，都不能提供这样一种必要信息：在随机输入在随机输入在随机输入在随机输入情况下，该算法具有怎样的行为（时间耗费）情况下，该算法具有怎样的行为（时间耗费）情况下，该算法具有怎样的行为（时间耗费）情况下，该

39、算法具有怎样的行为（时间耗费）。为此，引入。为此，引入。为此，引入。为此，引入平均效率平均效率平均效率平均效率 。平均效率分析要比最差和最优效率分析困难很多。以后讨论平均效率时平均效率分析要比最差和最优效率分析困难很多。以后讨论平均效率时平均效率分析要比最差和最优效率分析困难很多。以后讨论平均效率时平均效率分析要比最差和最优效率分析困难很多。以后讨论平均效率时都引用其已知的推导结果。对推导有兴趣的同学，请查阅有关书籍。都引用其已知的推导结果。对推导有兴趣的同学，请查阅有关书籍。都引用其已知的推导结果。对推导有兴趣的同学，请查阅有关书籍。都引用其已知的推导结果。对推导有兴趣的同学，请查阅有关书籍

40、。w w平均效率分析的价值平均效率分析的价值平均效率分析的价值平均效率分析的价值：有许多重要算法的平均效率比它们过于悲观的最差效率要好很多。有许多重要算法的平均效率比它们过于悲观的最差效率要好很多。有许多重要算法的平均效率比它们过于悲观的最差效率要好很多。有许多重要算法的平均效率比它们过于悲观的最差效率要好很多。所以所以所以所以如果没有平均效率分析的话，我们会错失不少重要的算法。显然，我们如果没有平均效率分析的话，我们会错失不少重要的算法。显然，我们如果没有平均效率分析的话，我们会错失不少重要的算法。显然，我们如果没有平均效率分析的话，我们会错失不少重要的算法。显然，我们不能通过求最优和最差效

41、率平均值的方法来求平均效率。不能通过求最优和最差效率平均值的方法来求平均效率。不能通过求最优和最差效率平均值的方法来求平均效率。不能通过求最优和最差效率平均值的方法来求平均效率。w w平均效率分析的直接法平均效率分析的直接法平均效率分析的直接法平均效率分析的直接法：1 1 将输入分为几种类型（可能的话），目的是使得对于同种输入类型的将输入分为几种类型（可能的话），目的是使得对于同种输入类型的将输入分为几种类型（可能的话），目的是使得对于同种输入类型的将输入分为几种类型（可能的话），目的是使得对于同种输入类型的 实例，具有相同的基本操作数。实例，具有相同的基本操作数。实例，具有相同的基本操作数。

42、实例，具有相同的基本操作数。2 2 得到或者假设各类输入的概率分布，以推导出基本操作的平均次数。得到或者假设各类输入的概率分布，以推导出基本操作的平均次数。得到或者假设各类输入的概率分布，以推导出基本操作的平均次数。得到或者假设各类输入的概率分布，以推导出基本操作的平均次数。但各类输入的但各类输入的但各类输入的但各类输入的概率模型概率模型概率模型概率模型往往又难以验证，虽然它可能很合理。往往又难以验证，虽然它可能很合理。往往又难以验证，虽然它可能很合理。往往又难以验证，虽然它可能很合理。13顺序查找算法的平均时间效率vv 顺序查找算法的平均时间效率：顺序查找算法的平均时间效率：顺序查找算法的平

43、均时间效率：顺序查找算法的平均时间效率：假设：假设：假设：假设：(1)(1)成功查找的概率是成功查找的概率是成功查找的概率是成功查找的概率是 p(0p1)p(0p1)，查找不成功的概率是，查找不成功的概率是，查找不成功的概率是，查找不成功的概率是 1-p1-p；(2)(2)对任意第对任意第对任意第对任意第 i i 次查找，第一次成功匹配（查找成功）发生在列表第次查找，第一次成功匹配（查找成功）发生在列表第次查找，第一次成功匹配（查找成功）发生在列表第次查找，第一次成功匹配（查找成功）发生在列表第 i i 个个个个位置的概率相同，即查找键位于列表任一位置上的概率相同位置的概率相同，即查找键位于列

44、表任一位置上的概率相同位置的概率相同，即查找键位于列表任一位置上的概率相同位置的概率相同，即查找键位于列表任一位置上的概率相同 1/n 1/n。基于。基于。基于。基于假设，在列表任一位置上查找成功的假设，在列表任一位置上查找成功的假设，在列表任一位置上查找成功的假设，在列表任一位置上查找成功的概率为概率为概率为概率为 p(1/n)p(1/n)（甚至可进一步假设（甚至可进一步假设（甚至可进一步假设（甚至可进一步假设p=0.5p=0.5）。若查找成功的位置为）。若查找成功的位置为）。若查找成功的位置为）。若查找成功的位置为 i i，算法做的比较次数（基本操作）为，算法做的比较次数（基本操作）为，算

45、法做的比较次数（基本操作）为，算法做的比较次数（基本操作）为i i 次，考虑成功查找概率，次，考虑成功查找概率，次，考虑成功查找概率，次，考虑成功查找概率，比较次数为比较次数为比较次数为比较次数为 p(i/n)p(i/n)；若查找不成功，算法做的；若查找不成功，算法做的；若查找不成功，算法做的；若查找不成功，算法做的比较次数为比较次数为比较次数为比较次数为 n n（列表全部查找一遍），考虑不成功查找概率，比较次数（列表全部查找一遍），考虑不成功查找概率，比较次数（列表全部查找一遍），考虑不成功查找概率，比较次数（列表全部查找一遍），考虑不成功查找概率，比较次数则为则为则为则为 n(1-p)n(

46、1-p)。因此，算法平均效率：。因此，算法平均效率：。因此，算法平均效率：。因此，算法平均效率：统统统统计计计计平平平平均均均均14摊销效率4 4 4 4 摊销效率摊销效率摊销效率摊销效率它并不适合于算法的单次运行，而应用于算法对同样数据的多次运行。它并不适合于算法的单次运行，而应用于算法对同样数据的多次运行。它并不适合于算法的单次运行，而应用于算法对同样数据的多次运行。它并不适合于算法的单次运行，而应用于算法对同样数据的多次运行。我们知道，在有些情况下单次运行的时间代价可能比较昂贵，但我们知道，在有些情况下单次运行的时间代价可能比较昂贵，但我们知道，在有些情况下单次运行的时间代价可能比较昂贵

47、，但我们知道，在有些情况下单次运行的时间代价可能比较昂贵，但 n n 次次次次运行的运行的运行的运行的总时间花费明显低于单次运行的最差效率乘以总时间花费明显低于单次运行的最差效率乘以总时间花费明显低于单次运行的最差效率乘以总时间花费明显低于单次运行的最差效率乘以 n n n n ，因此我们把，因此我们把，因此我们把，因此我们把最差效率的高成本摊到各次运行中去，即摊销效率。该做法与商业中最差效率的高成本摊到各次运行中去，即摊销效率。该做法与商业中最差效率的高成本摊到各次运行中去，即摊销效率。该做法与商业中最差效率的高成本摊到各次运行中去，即摊销效率。该做法与商业中把固定资产成本按其使用年限摊销到

48、整个序列（各年）中的做法一致。把固定资产成本按其使用年限摊销到整个序列（各年）中的做法一致。把固定资产成本按其使用年限摊销到整个序列（各年）中的做法一致。把固定资产成本按其使用年限摊销到整个序列（各年）中的做法一致。通常，具备这种运行特性的算法是在一定程度上的具有通常，具备这种运行特性的算法是在一定程度上的具有通常，具备这种运行特性的算法是在一定程度上的具有通常，具备这种运行特性的算法是在一定程度上的具有“智能智能智能智能”的算法，的算法，的算法，的算法，通过通过通过通过“学习学习学习学习”获得获得获得获得“知识知识知识知识”累积，再运用知识库中的有关知识对算法下次累积，再运用知识库中的有关知

49、识对算法下次累积，再运用知识库中的有关知识对算法下次累积，再运用知识库中的有关知识对算法下次如何执行提供指导，从而提高以后运行的效率。一个例子：汉字拼音如何执行提供指导，从而提高以后运行的效率。一个例子：汉字拼音如何执行提供指导，从而提高以后运行的效率。一个例子：汉字拼音如何执行提供指导，从而提高以后运行的效率。一个例子：汉字拼音输入法中的动态词频调整算法。它统计不同用户对某些字词的使用率输入法中的动态词频调整算法。它统计不同用户对某些字词的使用率输入法中的动态词频调整算法。它统计不同用户对某些字词的使用率输入法中的动态词频调整算法。它统计不同用户对某些字词的使用率（学习积累过程），来动态调整

50、这些字词下次出现的先后顺序，高频（学习积累过程），来动态调整这些字词下次出现的先后顺序，高频（学习积累过程），来动态调整这些字词下次出现的先后顺序，高频（学习积累过程），来动态调整这些字词下次出现的先后顺序，高频先现，达到减少用户翻阅时间的目的，提高了该算法的执行效率。先现，达到减少用户翻阅时间的目的，提高了该算法的执行效率。先现，达到减少用户翻阅时间的目的，提高了该算法的执行效率。先现，达到减少用户翻阅时间的目的，提高了该算法的执行效率。-后续章节中，除非专门说明，都将最差情况下时间耗费的极限作为算法后续章节中，除非专门说明，都将最差情况下时间耗费的极限作为算法后续章节中，除非专门说明，都将