第2讲 绪论（二）.

Presentation on theme: "第2讲 绪论（二）."— Presentation transcript:

1 第2讲 绪论（二）

2 教学目标 了解算法的基本概念及其特性； 熟练掌握时间复杂度的计算方法； 了解空间复杂度的计算方法。 2/14

3 1.4 算法与算法分析 算法 算法的特性 算法是对特定问题求解步骤的一种描述，它是指令的有限序列。 有穷性 确定性 可行性 有输入 有输出
1.4 算法与算法分析 算法 算法是对特定问题求解步骤的一种描述，它是指令的有限序列。 算法的特性 有穷性 确定性 可行性 有输入 有输出 in out 3/14

4 算法的设计原则 正确性 可读性 健壮性 效率与低存储量需求 4/14

5 算法效率的度量 度量方法 事后统计分析的方法 事前分析估算的方法 事前分析估算的方法的步骤 计算重复执行的次数 计算渐进时间复杂度 5/14

6 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.

7 时间复杂度计算举例-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)。 7/14

8 常见的时间复杂度，按数量级递增排序： 常数阶 对数阶 线性阶 线性对数阶 平方阶 立方阶 ……… K次方阶 指数阶

9 时间复杂度计算举例-2 例2：计算在一个含有n个元素的数组中查找某个元素的时间复杂度。 最坏时间复杂度 最好时间复杂度 平均时间复杂度
9/14

10 讨论题：分析下列两个算法完成 的功能并分别计算其时间复杂度
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; 10/14

11 空间复杂度 方法与计算时间复杂度类似，只是考虑执行算法所需的辅助空间。 11/14

12 小结 本讲首先介绍了算法的特性和算法设计的要求，然后重点介绍了算法的性能评价方法，特别是时间复杂度的计算方法。 12/14

13 作业与实验 作业 1．什么是算法？算法有哪些特性？ 2. 比较算法效率度量的事前分析估算的方法与事后统计分析的方法的不同。
2. 比较算法效率度量的事前分析估算的方法与事后统计分析的方法的不同。 3．计算下列算法的时间复杂度 void prime(int n){ for (i=2; i<=sqrt(n); i++) if (n %i==0) break; if (i>sqrt(n)) printf(“yes”); else printf(“no”); } 实验 无 13/14