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

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

1、第2章算法效率分析基础主要内容：2.1分析框架2.2渐进符号和基本效率类型2.3非递归算法的数学分析2.4递归算法的数学分析2021/9/261LingJie/GDUT2.1算法分析的基本框架一般而言，对于一个算法的分析主要是对算法效率的分析，包括了衡量其运行速度的时间效率以及衡量算法运行需要占用空间大小的空间效率。对于早期的计算机来说，时间与空间都是极其珍贵的资源。半个世纪以来，硬件技术的发展大大提高了计算机的存储容量，使得存储容量的局限性对于算法的影响大大降低了。但时间效率并没有得到相同程度的

2、提高。因此，算法的时间效率是算法分析中的关键部分。2021/9/262LingJie/GDUT2.1.1输入规模的度量一个显而易见的事实是：大部分算法的执行时间随着输入量的增加而增大。例如在对一个数组进行排序时，数组越大，排序需要的时间就越长。因此从逻辑上来说，算法的效率应该是输入量的函数。2021/9/263LingJie/GDUT2.1.2运行时间的度量单位算法时间包括了编译该算法的时间以及运行该算法的时间。因此衡量算法时间的单位很自然的会想到用“秒”、“毫秒”等实际的时间单位。这对于算法的测

3、试者而言是很直观的，但是存在的问题是：编译算法的时间与编译程序的好坏有关，即使只考虑算法运行时间，得到的时间也受到了运行该算法的计算机速度的影响。因此一个算法在某一台计算机上实现得到的时间对于其他的计算机是没有参考意义的。2021/9/264LingJie/GDUT统计算法每一步操作的执行次数——不可行。统计算法中最重要的操作—基本操作的执行次数。排序的基本操作：比较矩阵乘法的基本操作：乘法多项式求值的基本操作：乘法执行次数C(n)是输入规模n的函数，算法运行时间T(n)是执行次数的函数：2021

4、/9/265LingJie/GDUTBasicoperation:theoperationthatcontributesmosttowardstherunningtimeofthealgorithm.T(n)≈copC(n)runningtimeexecutiontimeforbasicoperationNumberoftimesbasicoperationisexecutedinputsize其中:cop为特定计算机上一个基本操作的执行时间，是常量。2021/9/266LingJie/GDUT2

5、.1.3增长次数小规模的输入在运行时间上不能区分高效的算法与低效的算法，要考虑对于大规模输入时执行次数的增长次数。nlog2nnlog2nn2n32nn!103.33.3×101021031033.6×1061026.66.6×1021041061.3×10303.6×10157103101.0×104106109105171.7×106101010152021/9/267LingJie/GDUT2.1.4算法最优、最差和平均效率算法最差效率：当输入规模为n时，算法在最坏情况下的效率。算法最优效率

6、：当输入规模为n时，算法在最理想情况下的效率。算法平均效率：在“随机”或“典型”输入时（规模仍为n），算法的效率。平均效率的研究方法：一般将规模为n的实例分为几种类型，在假设各种输入的概率分布，推导出基本操作的平均次数。2021/9/268LingJie/GDUT2.1小结:算法分析框架的要点算法的时间效率与空间效率都是算法输入量的函数。时间效率的衡量通过算法基本操作执行次数的估计进行，而空间效率的衡量是通过算法运行所占用额外的存储器资源量进行的。有些算法时空复杂度在相同输入量下可能由于具体输入值

7、的不同而不同，因此需要考虑最好情况下、最坏情况下以及一般情况下的算法时间复杂度。算法的分析框架关注的内容是当输入量很大，趋向无穷的时候，算法的时间复杂度是如何增长，即使用算法的时间复杂度的渐进表示法。2021/9/269LingJie/GDUT2.2渐进符号和基本效率类型三个渐进符号：常用函数符号：t(n)：一个算法运行的时间C(n)：基本操作次数g(n)：用来比较的函数2021/9/2610LingJie/GDUT1、三个渐进符号的定义O的定义：存在常数c＞0和非负整数n0，使得对所有nn0，

8、有t(n)cg(n)则称函数t(n)包含在O(g(n)中，记为t(n)∈O(g(n)).也称函数t(n)在n充分大时有上界g(n),并称t(n)的阶不高于g(n)的阶.例如，4nlogn+7∈O(nlogn)。2021/9/2611LingJie/GDUT2021/9/2612LingJie/GDUTΩ的定义：存在常数c＞0和非负整数n0，使得对所有nn0，有t(n)cg(n)则称函数t(n)包含在Ω(g(n)中，记为t(n)∈Ω(g(n))也称t(n)的阶不低于g(n)的阶