第2讲 绪论（二）
教学目标 了解算法的基本概念及其特性； 熟练掌握时间复杂度的计算方法； 了解空间复杂度的计算方法。
1.4 算法与算法分析 算法 算法的特性 算法是对特定问题求解步骤的一种描述，它是指令的有限序列。 有穷性 确定性 可行性 有输入 有输出 1.4 算法与算法分析 算法 算法是对特定问题求解步骤的一种描述，它是指令的有限序列。 算法的特性 有穷性 确定性 可行性 有输入 有输出 in out
算法的设计原则 正确性 可读性 健壮性 效率与低存储量需求
算法效率的度量 度量方法 事后统计分析的方法 事前分析估算的方法 事前分析估算的方法的步骤 计算重复执行的次数 计算渐进时间复杂度
Example of Big O notation: T(x) = O(f(x)) as there exists c > 0 (e Example of Big O notation: T(x) = O(f(x)) as there exists c > 0 (e.g., c = 1) and x0 (e.g., x0 = 5) such that T(x) ≤ cf(x) whenever x ≥ x0.
时间复杂度计算举例-1 for(i=1;i<=n;++i) for(j=1;j<=n;++j){ c[i][j]=0; 例1：求两个ｎ×ｎ矩阵乘积的时间复杂度。 for(i=1;i<=n;++i) for(j=1;j<=n;++j){ c[i][j]=0; for(k=1;k<=n;++k) c[i][j]+=a[i][k]*b[k][j]; } 分析：矩阵元素相乘是该问题中的基本操作，重复执行的次数为n3，算法时间复杂度为O(n3)。
常见的时间复杂度，按数量级递增排序： 常数阶 对数阶 线性阶 线性对数阶 平方阶 立方阶 ……… K次方阶 指数阶
时间复杂度计算举例-2 例2：计算在一个含有n个元素的数组中查找某个元素的时间复杂度。 最坏时间复杂度 最好时间复杂度 平均时间复杂度
讨论题：分析下列两个算法完成 的功能并分别计算其时间复杂度 long factor_sum(int n){ for (sum=0, i=1; i<=n; i++){ w=1; for (j=1; j<=i; j++) w=w×j; sum = sum+w; } return sum； long update_factor_sum(int n){ for(sum=0, w=1, i=1; i<=n; i++){ w=w×i; sum=sum+w; } return sum;
练习：分析以下程序段的时间复杂度 1.N×N矩阵相乘 for(i=1;i<=n;i++) for(j=1;j<=n;j++) {c[i][j]=0; for(k=1;k<=n;k++) c[i][j]=c[i][j]+a[i][k]*b[k][j]; } 2. i=1； while(i<=n) i=i*2;
空间复杂度 空间复杂度:算法所需存储空间的度量，记作: S(n)=O(f(n)) 其中n为问题的规模(或大小) 算法要占据的空间 算法本身要占据的空间，输入/输出，指令，常数，变量等 算法要使用的辅助空间
例：将一维数组a中的n个数逆序存放到原数组中。 S(n) = O(n) S(n) = O(1) 原地工作 【算法1】 for(i=0;i<n/2;i++) { t=a[i]; a[i]=a[n-i-1]; a[n-i-1]=t; } 【算法2】 for(i=0;i<n;i++) b[i]=a[n-i-1]; a[i]=b[i];
小结 本讲首先介绍了算法的特性和算法设计的要求，然后重点介绍了算法的性能评价方法，特别是时间复杂度的计算方法。
作业 1.描述算法所具备的基本特征，并指出算法与程序之间的差异。 2.试写一算法,自大到小依次输出顺序读入的三个数X,Y和Z的值。写出该算法的时间复杂度。 3.试写一算法,求出n个数据中的最大值。写出最大语句频度，该算法的时间复杂度。