第2讲 绪论（二）.

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

1 第2讲 绪论（二）

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

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

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

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

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)。

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

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

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;

11 练习：分析以下程序段的时间复杂度 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;

12 空间复杂度 空间复杂度:算法所需存储空间的度量，记作: S(n)=O(f(n)) 其中n为问题的规模(或大小) 算法要占据的空间
算法本身要占据的空间，输入/输出，指令，常数，变量等 算法要使用的辅助空间

13 例：将一维数组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];

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

15 作业 1.描述算法所具备的基本特征，并指出算法与程序之间的差异。
2.试写一算法,自大到小依次输出顺序读入的三个数X,Y和Z的值。写出该算法的时间复杂度。 3.试写一算法,求出n个数据中的最大值。写出最大语句频度，该算法的时间复杂度。