第2章 算法效率分析基础

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

1、1第2章算法效率分析基础一个问题往往有多个算法，应当分析算法的品性怎样评价一个算法？涉及的概念：问题的规模（大小）、基本操作、计算复杂度、复杂度的量级、上下界掌握循坏算法与递归算法的复杂度分析方法2正确性工作量空间用量简单性最优型34顺序查找：SequentialSearch(A[0..n-1],x)//输入：数组A[0..n-1],和查找关键字x//输出：返回第一个匹配x的元素下标//如果没有匹配的，返回-1i=0;whilei

2、查找关键字x56782.1分析框架如何评价时间效率？2.1.1输入规模的度量一个事实：问题规模越大，算法运行时间越长。将算法输入规模n为时间效率的参数。选择哪个（些）参数作为输入规模？9一个算法好不好体现在运行该算法所需要的计算机资源的多少上所需资源越少，该算法越好；计算机最重要的资源是时间和空间算法分析对算法利用这两种资源的效率做研究时间效率：指出正在讨论的算法运行得有多快；空间效率：关心算法需要的额外空间。研究实验告诉我们，对于大多数问题来说，我们在速度上能够取得的进展要远大于在空间上的进展，所以我们把主要精力集中在时间效率上。102.1.2运行时间的度量单位可以采用秒

3、，分，小时吗？可以统计算法每一步的操作次数吗？一般的做法：把基本操作（最重要的操作）次数作为算法运行时间的度量单位。思考下面算法的重要操作：排序矩阵乘法11建立一个算法时间效率的分析框架对于输入规模为n的算法统计基本操作执行次数C(n)，来对其效率进行度量。在某个特定计算机上的某个算法程序的运行时间T(n)≈copC(n)基本操作的执行时间基本操作次数12对下面的三个时间效率函数表达式,哪一个效率高?C1(n)=nC2(n)=n3C3(n)=10nn=11110n=228100n=33271000n=非常大结论：1随n的递增，不同函数增幅不同2某些函数在大规模时增幅显著，函

4、数可以表示增幅的特点3我们希望选择大规模时，时间效率增幅小的算法132.1.3增长次数（增长幅度）特别考虑大规模的输入要强调执行次数的增长次数呢？这是因为小规模输入在运行时间上差别不足以将高效的算法和低效的算法法区分开来。14图1－2各种函数的曲线152.1.4算法的最优、最差和平均效率一个算法的最差效率是指当输入规模为n时，算法的最坏情况下的效率。这时，相对于其他规模为n的输入，该算法的运行时间最长。为什么要考虑最坏效率？提供了对任何规模为n的实例，算法运行的上界Cworst(n)16一个算法的最优效率是指当输入规模为n时，算法在最优情况下的效率。这时，与其它规模为n的输

5、入相比，该算法运行得最快。然而，无论是最差效率分析还是最优效率分析都不能提供一种必要的信息：在“典型”或者“随机”输入的情况下，一个算法会具有什么样的行为。这正是平均效率试图提供给我们信息。17算法计算复杂度的定义182.1.5分析框架概要算法的时间效率和空间效率都用输入规模的函数进行度量。我们用算法基本操作的执行次数来度量算时间效率。通过计算算法消耗的额外存储单元的数量来度量空间效率。在输入规模相同的情况下，有些算法的效率会的显著差异。对于这样的算法，我们需要区分最差效率，平均效率和最优效率。本框架主要关心，当算法的输入规模趋向于无限大的时候，其运行时间（消耗的额外空间）

6、函数的增长次数。19复杂度函数的阶2.2渐进符号和基本效率类型2021例题2223注意上面3个符号O，θ，Ω称为渐进符号在问题的求解规模充分大的时候才成立。如，N3<2N,只有在N>c的时候才成立，其中c是方程N3＝2N的解。当N

7、率较差的部分.252.2.6利用极限比较增长次数虽然符号O，Ω和Θ的正式定义对于证明它们的抽象性质是不可缺少的，但我们很少直接用它们来比较两个特定函数的增长次数。有一种较为简便的比较方法，它是基于对所计论的两个函数的比率求极限。有3种极限情况会发生：262.2.7基本的效率类型O(2n)