算法2_算法分析基础

1、第2章 算法分析基础,学习要点：掌握算法分析中的算法复杂度概念时间复杂度、空间复杂度最好、最坏和平均情况时间复杂度掌握算法分析的渐近表示法掌握用C+语言描述算法的方法章节内容：2.1 算法复杂度2.2 渐近表示法2.3 递推关系（课外阅读）,2.1 算法复杂度,好算法的4个重要特征：Correctness正确性,注意区分“正确性”和“健壮性”的概念：算法正确性在合法的输入下，算法应实现预先规定的功能和计算精度要求。程序健壮性当输入不合法的数据时，程序应能做适当处理而不至于引起严重后果。正确性和健壮性互相补充。程序可靠性在正常情况下能正确地工作，在异常情况下也能做出适当处理。,2.1 算法复杂度,好算法的4个重要特征：Correctness正确性Simplicity, clarity简明性,遗憾的是，简单的算法不一定高效,思路清晰、层次分明、容易理解、利于编码和调试。,2.1 算法复杂度,好算法的4个重要特征：Correctness正确性Simplicity, clarity简明性Amount of time/space used效率,执行算法所需的时间和存储空间,算法设计者常常需要在算

2、法的简明性和效率之间作出谨慎的选择,2.1 算法复杂度,好算法的4个重要特征：Correctness正确性Simplicity, clarity简明性Amount of time/space used效率Optimality最优性,算法执行时间达到求解该类问题所需时间的下界。,与所求解问题自身的复杂程度有关。,For problem P, the algorithm A does at most WA(n) steps in the worst case (upper bound)F is a lower bound for a class of algorithm. (lower bound) If WA=F, then A is optimal.,Definition of the optimal algorithm（最优算法）,means that: For any algorithm in the class, and any input of size n, there is some input of size n for which the algorithm must

3、perform at least F(n) basic operations.,又如：可证排序问题的时间复杂度下界为(nlogn)。则最坏时间复杂性为O(nlogn)的排序算法是最优算法。因此：堆排序算法和两路合并排序算法都是最优算法。,例如:FindMax(int L) /求n个元素中的最大元素 int max=L0; int i=1; while(in) if (maxLi) max=Li; i=i+1; ,最优算法,影响程序运行时间的因素,程序所依赖的算法问题规模和输入数据计算机系统性能,根本的、起决定作用的,数值大小和状态,硬件系统性能（CPU速度）和软件系统性能（操作系统、编译器）,输入、输出,运行一个算法所需的时间和空间资源的量。算法的时间复杂性（Time Complexity）T(n)算法的空间复杂性（Space Complexity）S(n) 其中n是问题的规模（输入大小）,算法复杂度,How to Measure? Machine independentLanguage independentProgramming style independentImplement

4、ation independent,算法的时间复杂度,算法的时间复杂度算法运行所需的时间最好、最坏和平均时间复杂度,(不考虑计算机因素对算法分析的影响）,最好情况（出现概率较大时分析）最差情况（实时系统）平均情况（已知输入数据是如何分布的，通常假设等概率分布）,算法的时间复杂度,（1）最好情况下的时间复杂性：B(n) = Tmin(n) = min T(n,I) | IDn （2）最坏情况下的时间复杂性：W(n) = Tmax(n) = max T(n,I) | IDn （3）平均情况下的时间复杂性：A(n) = Tavg(n) =I:问题规模为n的实例。Dn :规模为n的所有合法输入的集合。p(I):实例I出现的概率。,算法的空间复杂度,算法的空间复杂度 算法运行所需的存储空间固定空间需求与所处理数据的大小和个数无关，即与问题实例的特征无关。（包括：程序代码、常量、简单变量、定长成分的结构变量所占的空间）可变空间需求与算法执行过程中处理的特定数据的规模有关。（如：数据元素所占的空间，算法执行所需的额外空间如递归算法所需系统栈空间）,通过程序步来分析算法的时间复杂度,求数组元素累加之和

5、的迭代程序：(P20 程序2-1)float Sum(float list,const int n) float tempsum=0.0;/1 for (int i=0;i0，则f(n)=O(nm)。,例如：程序2-1float Sum(float list,const int n) float tempsum=0.0;/1 for (int i=0;in;i+)/n+1 tempsum+=listi;/n return tempsum;/1,可以通过考察一个程序中关键操作（key operation）的执行次数，来估算算法的渐近时间复杂度。,关键操作！执行次数n和总的程序步2n+3有相同的渐近时间复杂度O(n)。,关键操作通常是位于算法最内层循环的程序步（或语句），是算法中执行次数最多的操作（程序步） 。,可以通过考察一个程序中关键操作（key operation）的执行次数，来估算算法的渐近时间复杂度。,关键操作通常是位于算法最内层循环的程序步（或语句），是算法中执行次数最多的操作（程序步） 。,例如：程序2-3 矩阵乘法for (i=0;in;i+)/n+1 for (j=0;j

6、n;j+)/n(n+1) cij=0;/n2for (k=0;kn) Swap(m,n);while (m0) int c=n%m; n=m; m=c;return n;,有时候算法时间的计算并非直截了当，while循环每次迭代后余数值并非按常数因子递减。如何计算迭代次数？,定理2-2 如果nm ，则n mod m 0，则f(n)=(nm)。,（3）紧渐近界记号 如果存在正常数c1,c2和n0，使得当n n0时有c1g(n)f(n) c2g(n)，则称函数f(n)与函数g(n)同阶，记做f(n)(g(n)。即f(n)与g(n)的增长阶数相同。,(g(n) = O(g(n) (g(n) 即：f(n) = (g(n) 当且仅当 f(n) = O(g(n) 且 f(n) = (g(n),证明 （略）,（定理2-4） 如果f(n)=amnm+am-1nm-1+a1n+a0是m次多项式，且am0，则f(n)=(nm)。,（4）非紧上界记号o如果对于任何正常数c0都存在正整数n0 0，使得当n n0时有f(n)cg(n) （等价于:n时，f(n) / g(n) 0），则称函数f(n)当n充分大时的阶比g(n)低，记做f(n)=o(g(n)。,（5）非紧下界记号 如果对于任何正常数c0都存在正整数n0 0，使得当n n0时有f(n)cg(n) （等价于n时，f(n)/g(n)），则称函数f(n)当n充分大时的阶比g(n)高，记做f(n)(g(n)。,

《算法2_算法分析基础》由会员壹****1分享，可在线阅读，更多相关《算法2_算法分析基础》请在金锄头文库上搜索。