第1章绪论 1.3算法分析《算法与数据结构（C＆Java）（第2版）》 同步教学（电子工业出版社）

什么是数据结构 基本概念和术语 算法和算法分析 第一章 绪论 三、算法分析 时间复杂度 1、时间频度 一个算法执行所耗费的时间，从理论上是不能算出来的，必须上机运行测试才能知道。但我们不可能也没有必要对每个算法都上机测试，只需知道哪个算法花费的时间多，哪个算法花费的时间少就可以了。并且一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)。 算法分析的目的在于选择合适算法和改进算法。一个算法的评价主要从时间复杂度和空间复杂度来考虑。 例1 求下列算法段的语句频度 for(i=1; i<=n; i++) for(j =1; j<=i ; j++) x=x+1; 分析：该算法为一个二重循环，执行次数为内、外循环次数相乘，但内循环次数不固定，与外循环有关， 因些，时间频度T(n) = 1+2+3+…+n = 2、时间复杂度 在刚才提到的时间频度中，n称为问题的规模，当n不断变化时，时间频度T(n)也会不断变化。但有时我们想知道它变化时呈现什么规律。为此，我们引入时间复杂度概念。 一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n),使得当n趋近于无穷大时，T(n)/f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。记作T(n)=Ｏ(f(n))，称Ｏ(f(n)) 为算法的渐近时间复杂度，简称时间复杂度。 例如，若T(n)=n(n+1)/2，则有 1/4≤T(n)/n2≤1，故它的时间复杂度为Ｏ(n2), 即Ｔ(n)与n2 数量级相同。 算法效率的度量：采用时间复杂度 例1.2 分析以下程序段的时间复杂度 for (i=1;i<n;i++) { y=y+1; for (j=0; j<=(2*n); j++) x++; } /* 语句1 * / /* 语句2 * / 分析：语句的频度指的是该语句重复执行的次数。一个算法中所有语句的频度之和构成了该算法的运行时间。 语句1的频度是：n-1 语句2的频度是： 则该程序段的时间复杂度： T(n)= 例1.3 分析以下程序段的时间复杂度 i=1; while (i<=n) i=i*2 语句1的频度是：1 设语句2的频度是f(n)，则有： 即， 取最大值： 则该程序段的时间复杂度为： /* 语句1 * / /* 语句2 * / 例1.4 x=1; for (i=1;i<=n;i++) for (j=1;j<=i;j++) for (k=1;k<=j;k++) x++; 由于内循环的执行次数虽与规模n无直接关系，但与外循环的变量取值有关。因此从内层向外层循环分析执行次数。 分析算法规律可知时间频度 T(n)=1+(1+2)+(1+2+3)+...+(1+2+3+…+n) = = = + = [ + ] 由于有1/6 ≤ T（n)/ n3 ≤1，故时间复杂度为Ｏ(n3)。 常见函数的时间复杂度按数量递增排列及增长率 常数阶O(1) 对数阶O(log2n) 线性阶O(n) 线性对数阶O(nlog2n) 平方阶O(n2) 立方阶O(n3) …… k次方阶O(nk) 指数阶O(2n) 四、空间复杂度 与时间复杂度类似，空间复杂度是指算法在计算机内执行时所需存储空间的度量。记作: S(n)=O(f(n)) 我们一般所讨论的是除正常占用内存开销外的辅助存储单元规模。讨论方法与时间复杂度类似，不再赘述。 函数 如果将算法理解成思想，那么函数是程序的一部分，是实现算法的载体。 在C语言中函数的定 义也严格规范，其具体格式如下： 函数的返回类型 函数名（形式参数） { 说明语句 执行语句 } 在C语言中，函数的定义不可以嵌套，但函数可以嵌套调用自身，这称为递归调用，递归调用在实际编程中得到广泛应用，下列函数是求整数n的阶乘，该函数一个整型参数n，返回值为整型，n的阶乘。 1 int fac(n){ 2 if n==1 return 1; 3 else return n*fac(n-1); 4 } 递归函数在本课程中将会经常