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

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

1、第2章算法效率分析基础一个问题往往有多个算法应当分析算法的品性怎样评价一个算法？1一个算法好不好体现在运行该算法所需要的计算机资源的多少上所需资源越少，该算法越好；计算机最重要的资源是时间和空间算法分析对算法利用这两种资源的效率做研究时间效率：指出正在讨论的算法运行得有多快；空间效率：关心算法需要的额外空间。研究实验告诉我们，对于大多数问题来说，我们在速度上能够取得的进展要远大于在空间上的进展，所以我们把主要精力集中在时间效率上。22.1分析框架如何评价时间效率？2.1.1输入规模的度量一个事实：问题规模越大，算法运行时间越长。将算

2、法输入规模n为时间效率的参数。选择哪个（些）参数作为输入规模？32.1.2运行时间的度量单位可以采用秒，分，小时吗？可以统计算法每一步的操作次数吗？一般的做法：把基本操作（最重要的操作）次数作为算法运行时间的度量单位。思考下面算法的重要操作：排序矩阵乘法4建立一个算法时间效率的分析框架对于输入规模为n的算法统计基本操作执行次数C(n)，来对其效率进行度量。在某个特定计算机上的某个算法程序的运行时间T(n)≈copC(n)基本操作的执行时间基本操作次数5对下面的三个时间效率函数表达式,哪一个效率高?C1(n)=nC2(n)=n3C3(

3、n)=10nn=11110n=228100n=33271000n=非常大结论：1随n的递增，不同函数增幅不同2某些函数在大规模时增幅显著，函数可以表示增幅的特点3我们希望选择大规模时，时间效率增幅小的算法62.1.3增长次数（增长幅度）特别考虑大规模的输入要强调执行次数的增长次数呢？这是因为小规模输入在运行时间上差别不足以将高效的算法和低效的算法法区分开来。7图1－2各种函数的曲线8C(n)可以合理的度量算法的效率，但对同一个算法相同的规模下运行时间就一样吗？考虑顺序查找：SequentialSearch(A[0..n-1],K)/

4、/输入：数组A[0..n-1],和查找关键字K//输出：返回第一个匹配K的元素下标//如果没有匹配的，返回-1i=0WhileiKdoi=i+1Ifi

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

6、算法的输入规模趋向于无限大的时候，其运行时间（消耗的额外空间）函数的增长次数。122.2渐进符号和基本效率类型2.2.1非正式的介绍非正式来说，O(g(n))是增长次数小于等于g(n)(以及其常数倍，n趋向于无穷大)的函数集合。考虑O(n2)n∈O(n2),100n+5∈O(n2),1/2(n(n-1))∈O(n2),n3不属于O(n2),13第二个符号Ω(g(n))，代表增长次数大于等于g(n)(以及其常数倍,n趋向于无穷大)的函数集合。n3∈Ω(n2)，1/2(n(n-1))∈Ω(n2)，但是100n+5∈Ω(n2)14最后，Θ

7、(g(n))是增长次数等于g(n)(以及其常数倍,n趋向于无穷大)的函数集合。例：每一个二次方程an2+bn+c在a>0的情况下都包含在Θ(n2)中。152.2.2符号О定义1把函数t(n)包含在O(g(n))中记作t(n)∈O(g(n))。称t(n)的阶不高于g(n)的阶.成立条件：对于所有足够大的n，t(n)的上界由g(n)的常数倍数所确定。即，存在大于0的常数c和非负的整数n0，使得：对于所有的n≥n0来说，t(n)≤cg(n)n0之前的情况无关重要,为什么？cg(n)t(n)n符号O：t(n)∈O(g(n))n0常用函数符号

8、：t(n)一个算法运行的时间函数C(n)基本操作次数函数g(n)用来比较的函数16t(n)=3n+2。说明属于O(n)当n≥n0=2时，3n+2≤3n+n＝4n此时c=4,g(n)=n。（向定义式靠拢）t(n)≤4g(n)t(n)∈O