第1章 绪论（二） 教学目标 理解算法的特性及评价标准 掌握算法时间复杂度和空间复杂度的分析方法 1/

Presentation on theme: "第1章 绪论（二） 教学目标 理解算法的特性及评价标准 掌握算法时间复杂度和空间复杂度的分析方法 1/"— Presentation transcript:

1 第1章 绪论（二） 教学目标 理解算法的特性及评价标准 掌握算法时间复杂度和空间复杂度的分析方法 1/

2 算法和算法分析 算法定义 特性 是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每个指令表示一个或多个操作。
①有穷性：算法中执行的步骤总是有限次数的，不能无休止的执行下去． ②确定性：算法中的每一步操作的内容和顺序必须含义确切，不能有二义性． 算法与程序：(1).一个程序不一定满足有穷性。例操作系统，只要整个系统不遭破坏，它将永远不会停止，即使没有作业需要处理，它仍处于动态等待中。因此，操作系统不是一个算法。(2).程序中的指令必须是机器可执行的，而算法中的指令则无此限制。(3).算法代表了对问题的解，而程序则是算法在计算机上的特定的实现。一个算法若用程序设计语言来描述，则它就是一个程序. 歧义：① 公园里有三个幼儿园的孩子。（有三个孩子，他们是幼儿园的／孩子属于三个幼儿园） ② 我借他一本书。（我借给他一本书／我从他那里借来一本书） 去不去？ 算法，思路的区别 2/

3 算法和算法分析 特性 ③可行性：即算法中的每一步能通过手工和机器在有限时间内完成，也称之为有效性．
④有输入：一个算法中有零个或多个输入，这些输入数据应在算法操作前提供． ⑤有输出：一个算法有一个或多个输出．算法的目的是用来解决一个给定的问题，因此它应向人们提供产生的结果，否则就没有意义了． 3/

4 算法和算法分析 算法设计的要求 算法的描述： 自然语言 正确性 可读性 健壮性 思考：算法与程序的区别？ 高效率与低存储量需求
流程图 程序设计语言 伪码 思考：算法与程序的区别？ 算法与程序：(1).一个程序不一定满足有穷性。例操作系统，只要整个系统不遭破坏，它将永远不会停止，即使没有作业需要处理，它仍处于动态等待中。因此，操作系统不是一个算法。(2).程序中的指令必须是机器可执行的，而算法中的指令则无此限制。(3).算法代表了对问题的解，而程序则是算法在计算机上的特定的实现。一个算法若用程序设计语言来描述，则它就是一个程序. 健壮性的意思就是对不同的输入都要有相应的反应，比如合法的输入就要有相应的输出，不合法的输入要有相应的提示信息输出，提示此输入不合法！ 4/

5 算法和算法分析 求1+2+3+…… 的结果 5/

6 算法和算法分析 算法效率的度量 度量一个程序的执行时间的方法 事后统计的方法 事前分析估算的方法 依据的算法选用何种策略 问题的规模
书写程序的语言 编辑程序所产生的机器代码的质量 机器执行指令的速度 6/

7 算法和算法分析 时间复杂度 一个算法所耗费的时间，应该是该算法中每条语句的执行时间之和，而每条语句的执行时间又是该语句的执行次数（频度）与该语句执行一次所需时间的乘积。 假定每条语句一次执行的时间都是相同的，为单位时间。这样对时间的分析就可以独立于软硬件系统。 7/

8 算法和算法分析 算法分析： 假定每条语句的执行时间为单位时间。算法的时间复杂度是该算法中所有语句的执行频度之和。
例：求两个方阵的乘积 C＝A*B 8/

9 算法和算法分析 ＃define n 自然数 MATRIXMLT(float A[n][n],float B[n][n],float C[n][n]) { int i, j, k; for(i=0;i<n;i++) for(j=0;j<n;j++) C[i][j]=0; for( k=0;k<n;k++) C[i][j]=A[i][k]*B[k][j]+ C[i][j] } // n+1 // n(n+1) // n*n // n*n*(n+1) // n*n*n 9/

10 算法中重复执行次数和算法的执行时间成正比的语句
时间复杂度的渐进表示法 算法中基本语句重复执行的次数是问题规模n的某个函数f(n),算法的时间量度记作： T(n)=O(f(n)) 算法中重复执行次数和算法的执行时间成正比的语句 对算法运行时间的贡献最大 表示随着n的增大，算法执行的时间的增长率和f(n)的增长率相同，称渐近时间复杂度。 n越大算法的执行时间越长 排序：n为记录数 矩阵：n为矩阵的阶数 多项式：n为多项式的项数 集合：n为元素个数 树：n为树的结点个数 图：n为图的顶点数或边数

11 分析算法时间复杂度的基本方法 x = 0; y = 0; for (k = 0; k < n; k ++ ) x ++;
找出语句频度最大的那条语句作为基本语句 计算基本语句的频度得到问题规模n的某个函数f(n) 取其数量级用符号“O”表示 x = 0; y = 0; for (k = 0; k < n; k ++ ) x ++; for (i = 0; i < n; i++ ) for (j = 0; j < n; j++ ) y ++; T(n) = O(n2) f(n)=n2

12 时间复杂度是由嵌套最深层语句的频度决定的
void exam ( float x[ ][ ], int m, int n ) { float sum [100];int i,j; for (i = 0; i < m; i++ ) { sum[i] = 0.0; for (j = 0; j < n; j++ ) sum[i] += x[i][j]; } for ( i = 0; i < m; i++ ) printf(“%.1f\n”, sum [i]); T(n) = O(m*n) f(n)=m*n

13 例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]; } 算法中的基本操作语句为c[i][j]=c[i][j]+a[i][k]*b[k][j];

14 语句频度 = 例2： 定理1.1 for( i=1; i<=n; i++)
for (j=1; j<=i; j++) for (k=1; k<=j; k++) 　　　　x=x+1; 定理1.1 若f(n)=amnm+am-1nm-1++a1n+a0是m次多项式，则T(n)=O(nm)。 忽略所有低次幂项和最高次幂系数，体现出增长率的含义 语句频度 =

15 例3：分析以下程序段的时间复杂度 i=1; ① while(i<=n) i=i*2; ②
即f(n)≤log2n，取最大值f(n)=log2n 所以该程序段的时间复杂度T(n) =O( log2n)

16 有的情况下，算法中基本操作重复执行的次数还随问题的输入数据集不同而不同
例4：顺序查找，在数组a[i]中查找值等于e的元素，返回其所在位置。 for (i=0;i< n;i++) if (a[i]==e) return i+1; return 0; 最好情况：1次 最坏情况：n 平均时间复杂度为:O(n)

17 　当n取得很大时，指数时间算法和多项式时间算法在所需时间上非常悬殊
时间复杂度T(n)按数量级递增顺序为： 复杂度低 复杂度高

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

19 S(n) = O(1) 原地工作 例5：将一维数组a中的n个数逆序存放到原数组中。 S(n) = O(n) 【算法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];

20 例 若矩阵Am×n中存在某个元素aij满足：aij是第i行中最小值且是第j行列中的最大值，则称该元素为矩阵A的一个鞍点，试编写算法找出A中的所有鞍点。
算法一 用穷举法 对每一个元素aij进行判别 若aij是第i行的最小数，则继续判别，看它是否也是第j列的最大数，如果成立则是鞍点。 当aij不是第i行的最小数或者不是第j列的最大数则选择下一个元素继续。 矩阵A用一个二维数组表示，算法如下页所示： 20/

21 void saddle ( int A[m][n]) /*求m行n列矩阵的鞍点*/
#define m 10 #define n 10 void saddle ( int A[m][n]) /*求m行n列矩阵的鞍点*/ { int i,j,k，smin,smax；/* smin 为true时表示A[i][j]是第i行最小数，smax 为true时表示A[i][j]是第j列的最大数 */ for (i=0；i<m；i++ ) /* 用枚举法对矩阵的每个元素进行判断*/ for (j=0；j<n；j++ ) { k=0； while ( k<n )&& (A[i][k ] >= A[i][j] ) /*是否是第i行最小数*/ k++; if (k<n) smin=false; else smin=true; if ( smin ==true) /*是第i行最小数时继续判断*/ { k=0； while (k<m) && (A [k] [j]<=A [i][j] ) /*是否是第j列最大数*/ if (k<m) smax=false; else smax=true; } if ( smin==true && smax==true ) printf ( “\nA[%d][%d]是鞍点” ,i,j) ; /* A [i j] 是鞍点。*/ }//end for j } //end for i 21/

22 算法和算法分析 时间效率： 双重循环体内有两个并列的while循环语言。第一个while循环执行O (n )次，第二个while循环最多执行O（m）次。所以总的时间效率应该是O (m*n*( m+n)) 空间效率： 除矩阵A用二维数组存贮外，用了几个辅加空间作为中间变量。所以空间效率为O（1） 22/

23 算法二 先将矩阵每行最小数和每列的最大数求出来，并存放在B[n]和C[m]两个一维数组中见下图。
23/

24 然后对B[n]和C[m]的每对元素进行比较，假定B[j]和C[i]相等（见下图），则A[i][j]一定是鞍点。
24/

25 void Saddle ( int A[m][n]) { int i ，j ，k； int B [n]，C[m]； for ( i=0；i<m；i++ ) /* 求每行的最小数 */ { C[i]=A[i][0]； for ( j=1；j<n；j++ ) if C[i]>A[i][j] C[i]=A[i][j] ｝ for (j = 0；j<n；j++ ) /*求每列的最大数*/ B[j] = A[0][j]； for ( i = 1；i<m；i++ ) if (B[j]<A[i][j]) B[j] = A[i][j]； } /*求所有鞍点 */ 25/

26 printf ( “\nA[%d][%d]是鞍点” ,i,j) ; /* A [i j] 是鞍点。*/ }
for ( i = 0；i<m；j++ ) for ( j = 0；j<n；j++ ) if ( C[i] = =B[j]) printf ( “\nA[%d][%d]是鞍点” ,i,j) ; /* A [i j] 是鞍点。*/ } 26/

27 算法和算法分析 时间效率 空间效率为： O (M + N ) 比较这两种算法，显然方法二的时间效率大大优于方法一，但空间效率较差。
本算法共有三个循环 求每行的最小数时间效率 O ( M*N ) 求每列的最大数时间效率 O (M*N) 打印所有鞍点时间效率 O (M*N) 总的时间效率 O (M*N ) 空间效率为： O (M + N ) 比较这两种算法，显然方法二的时间效率大大优于方法一，但空间效率较差。 算法二是典型的牺牲空间效率换取时间效率。 27/

28 算法和算法分析 判断某某年是不是闰年 这是通过一笔空间上的开销来换取计算时间的小技巧。到底哪一个好，其实要看你用在什么地方。
方法一：每次给一个年份，都是要通过计算得到是否是闰年的结果。 方法二：事先建立一个有 2050 个元素的数组(年数略比现实多一点) ，然后把所有的年份按下标的数字对应，如果是闰年，此数组项的值就是 1 ，如果不是值为 0。这样，所谓的判断某一年是否是闰年，就变成了查找这个数组的某一项的值是多少的问题。 此时，我们的运算是最小化了，但是硬盘上或者内存中需要存储这 2050 个 0 和 1。 这是通过一笔空间上的开销来换取计算时间的小技巧。到底哪一个好，其实要看你用在什么地方。 28/

29 小结 算法的定义 算法的特性 算法的设计的要求 算法时间复杂度的定义和推导大 0 阶的步骤。
算法是解决特定问题求解步骤的描述，在计算机中为指令的有限序列，并且每条指令表示一个或多个操作。 算法的特性 有穷性、确定性、可行性、输入、输出 。 算法的设计的要求 正确性、可读性、健壮性、 高效率和低存储量需求。 算法时间复杂度的定义和推导大 0 阶的步骤。 29/

30 本章小结 在用计算机解题过程中，算法和数据结构是相辅相成、缺一不可的两个方面。数据结构是算法处理的对象也是设计算法的基础。一个具体问题的数据在计算机中往往可以采用多种不同的数据结构来表示；一个计算过程的实现又常常有多种可用的算法。因此选择什么样的算法和数据结构就成为实现程序过程中最重要的一个课题。 抽象数据类型的引入，提高了程序设计的抽象层次，也为数据结构和算法的研究提供了一种分层的模型。 重点掌握数据结构和算法的基本知识，理解它们在问题求解中的作用；了解下述概念：数据的逻辑结构、存储结构和操作，抽象数据类型，数据结构和算法的特性，算法的分析，空间代价和时间代价等。 30/

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