《事前分析估算的方法》由会员分享，可在线阅读，更多相关《事前分析估算的方法（3页珍藏版）》请在金锄头文库上搜索。
1、事前分析估算的方法假设给定的是一台通用计算机，满足：口执行一条基本语句或一个基本运算需花一个单位时间口基本语句指：赋值语句、输入语句、输出语句口基本运算指：算术运算、一次比较(字符比较、数值比较)做法：从算法中选取一种对于所研究的问题(或算法类型)来说是基本操作的原操作，以 该基本操作重复执行的次数作为算法的时间量度。例8-1两个NXN矩阵A和B相乘的算法。for (i=0;in;i+)for (j=0;jn;j+)cij=0;for (k=0;kn0时都 满足|xn|Mfn)|；(换句话就是说，这当整型自变量n趋向于无穷大时，两者的比值是一个 不等于0的常数。)例8-2 NXN矩阵相乘的算法
2、的时间复杂度：基本操作执行的次数：nXnXn=n3. T(n)=O(n3)口语句的频度：是指该语句重复执行的次数。与该语句包含的基本操作执行的次数相同。例8分析语句+x; s=0;的频度。解：将+x”看成是基本操作，则语句频度为1，即时间复杂度为。(1)；如果将“s=0”也看 成是基本操作，则语句频度为2,其时间复杂度仍为0(1)，即常量阶。例 9 分析语句 for (i=1; i=n; +i)+x; s+=x;解：语句频度为：2n，其时间复杂度为：T(n)=O(n)。即时间复杂度为线性阶。例 10 分析语句 for (i=1; i=n; +i)for (j=1; j=n; +j)+x; s+
3、=x;解：语句频度为：2n2,其时间复杂度为：O(n2)。即时间复杂度为平方阶。口 定理：若 A(n)=amnm +am1nm-1 +a1n+a0 是一个 m 次多项式，则 A(n)=O(n m)。(证明 略)m例 11 for (i=2; i=n; +i)for (j=2; j= (y + 1)(y + 1)(y+;以下六种计算算法时间复杂度的多项式是最常用的。其关系为：O(1)O(logn)O(n)O(nlogn)O(n2)O(n3)指数时间的关系为：O(2n)O(n!)1 & change;-i)(change=false;for(j=0;jaj+1) aj-aj+1;change=TU
4、RE分析：口问题的输入规模：n；口基本操作：“交换序列中相邻两个整数”；实例：5 1 9 7 3 23 1 2 5 9 7口 “基本操作”数随n变化的规律：-a中序列自小至大有序时，“基本操作”数为0；-a中序列自大至小有序时，“基本操作”数为=(1+2+3+.+(n-1)=n(n-1)/2口 算法的时间复杂度：-最好情况下的时间复杂度：0-最坏情况下的时间复杂度：W(n) =n(n-1)/2-平均情况下的时间复杂度：AV(n) = 1/n!0+1+2+n(n-1)/2=O(n2)总结：确定算法问题规模；找出基本操作；分析基本操作是否只依赖于问题规模？口是，就直接建立基本操作执行次数的求和表达式，并求解、用渐进符号表示;口否则，分别对该算法的最好、最坏和平均情况的时间复杂度进行分析。口算法的存储空间代价 一个算法的空间效率是指在算法的执行过程中，所占据的辅助空间数量。空间复杂度：算法所需存储空间的度量，记作S(n)=O(f(n)其中，n为问题的规模。
