算法及算法分析2

1、算法及算法分析 算法算法是对特定问题求解步骤的一种描述，它是指令的有限序列指令的有限序列，其中每一条指令表示一个或多个操作。一个算法应满足以下五个重要特性五个重要特性：1 1有穷性有穷性 2 2确定性确定性 3 3可行性可行性4 4有输入有输入 5 5有输出有输出算法算法1 1有穷性有穷性 对于任意一组合法输入值，在执行有穷步骤有穷步骤之后一定能结束，即：算法中的每个步骤都能在有限时间有限时间内完成； 2 2确定性确定性 对于每种情况每种情况下所应执行的操作，在算法中都有确切确切的规定，使算法的执行者或阅读者都能明确其含义及如何执行。并且并且在任何条件下，算法都只有一在任何条件下，算法都只有一

2、条执行路径；条执行路径；例: (1)begin (2)n=1 (3)n=n+1 (4)repeat (3) (5)end例: (1)begin (2)n=1 (3)n=n+1 (4)if n=100 do (5),else repeat(3) (5)output n (6)end3 3可行性可行性 算法中的所有操作都可以通过已经实现的基本操作运算有限次实现之；4 4有输入有输入 输入作为算法加工对象的量值，通常体现为算法中的一组变量。有些输入量需要在算法执行过程中输入，而有的算法表面上可以没有输入，实际上已被嵌入算法之中； 5 5有输出有输出 它是一组与“输入”有确定关系的量值，是算法进行信息

3、加工后得到的结果，这种确定关系即为算法的功能。课堂思考例：从n个整数元素中找出最大值。文字描述流程图算法设计的原则算法设计的原则设计算法时，通常应考虑达到以下目标：设计算法时，通常应考虑达到以下目标：1正确性正确性2. . 可读性可读性3健壮性健壮性4高效率与低存储量需求高效率与低存储量需求 c c程序对于精心选择的、典型、苛刻且带有刁难性程序对于精心选择的、典型、苛刻且带有刁难性的几组输入数据能够得出满足要求的结果；的几组输入数据能够得出满足要求的结果； 通常以第 c c 层意义的正确性作为衡量一个算法是否合格的标准。 d d程序对于一切合法的输入数据都能得出满足要求程序对于一切合法的输入数

4、据都能得出满足要求 的结果；的结果；a a程序中不含语法错误；程序中不含语法错误；b b程序对于几组输入数据能够得出满足要求的结果；程序对于几组输入数据能够得出满足要求的结果；2. . 可读性可读性 算法主要是为了人的阅读与交流阅读与交流，其次才是为计算机执行。因此算法应该易易于人的理解于人的理解；另一方面，晦涩难读的程序易于隐藏较多错误而难以调试；例：例：a = ab； b = ab； a = ab；3健壮性健壮性 当输入的数据当输入的数据非法非法时，算法应当恰当时，算法应当恰当地作出反映或进行相应处理，而不是产地作出反映或进行相应处理，而不是产生莫名奇妙的输出结果。并且，处理出生莫名奇妙的

5、输出结果。并且，处理出错的方法不应是中断程序的执行，而应错的方法不应是中断程序的执行，而应是返回一个表示错误或错误性质的值，是返回一个表示错误或错误性质的值，以便在更高的抽象层次上进行处理。以便在更高的抽象层次上进行处理。4高效率与低存储量需求高效率与低存储量需求 通常，效率指的是算法执行时间；存储量指的是算法执行过程中所需的最大存储空间。两者都与问题的规模有关。 同一问题可以采用多种算法实现。如何同一问题可以采用多种算法实现。如何比较算法执行效率？比较算法执行效率？ 算法描述的语言不同算法描述的语言不同 算法执行的环境不同算法执行的环境不同 其他因素其他因素 所以不能用绝对执行时间进行比较所

6、以不能用绝对执行时间进行比较 算法执行时间需通过依据该算法编制的程序在算法执行时间需通过依据该算法编制的程序在计算机上运行所消耗的时间来度量。其方法通常有两种：计算机上运行所消耗的时间来度量。其方法通常有两种：事后统计事后统计：计算机内部进行执行时间和实际占用空间的：计算机内部进行执行时间和实际占用空间的统计。统计。 问题：必须先运行依据算法编制的程序；依赖问题：必须先运行依据算法编制的程序；依赖软硬件环境，容易掩盖算法本身的优劣；没有实际价值。软硬件环境，容易掩盖算法本身的优劣；没有实际价值。事前分析事前分析：求出该算法的一个时间界限函数。：求出该算法的一个时间界限函数。1.3.3 算法效率

7、的度量算法效率的度量与此相关的因素有：与此相关的因素有： 依据算法选用何种策略；依据算法选用何种策略； 问题的规模；问题的规模； 程序设计的语言；程序设计的语言； 编译程序所产生的机器代码的质量；编译程序所产生的机器代码的质量； 机器执行指令的速度；机器执行指令的速度； 撇开软硬件等有关部门因素，可以认为一个特定撇开软硬件等有关部门因素，可以认为一个特定算法算法“运行工作量运行工作量”的大小，只依赖于问题的规模的大小，只依赖于问题的规模（通常用（通常用n n表示），或者说，它表示），或者说，它是问题规模的函数是问题规模的函数。 算法中算法中基本操作重复执行的次数基本操作重复执行的次数是问题规模

8、是问题规模n n的某个函数，其时间量度记作的某个函数，其时间量度记作 T(n)=O(f(n)T(n)=O(f(n)，称作，称作算法的渐近时间复杂度算法的渐近时间复杂度( (Asymptotic Time complexityAsymptotic Time complexity) )，简称简称时间复杂度时间复杂度。 一般地，常用一般地，常用最深层循环内最深层循环内的语句中的原操作的语句中的原操作的的执行频度执行频度( (重复执行的次数重复执行的次数) )来表示。来表示。 “O”O”的定义：的定义： 若若f(n)f(n)是正整数是正整数n n的一个函数，则的一个函数，则 O(f(n)O(f(n)表

9、示表示 M M0 0 ，使得当，使得当n n n n0 0时，时，| f(n) | | f(n) | M M | f(n| f(n0 0) | ) | 。表示表示时间复杂度时间复杂度的阶有：的阶有： O(1)O(1) ：常量时间阶：常量时间阶 O (n)O (n)：线性时间：线性时间阶阶 O(O(n)n) ：对数时间阶：对数时间阶 O(nO(nn)n) ：线性对数时：线性对数时间阶间阶算法分析应用举例 O (nO (nk k) )： k k2 2 ，k k次方时间阶次方时间阶例例 两个两个n n阶方阵的乘法阶方阵的乘法 for(i=1for(i=1，i=n; +i)i=n; +i) for(j

10、=1; j=n; +j) for(j=1; j=n; +j) cij=0 ; cij=0 ; for(k=1; k=n; +k) for(k=1; k=n; +k) cij+=aikcij+=aik* *bkj ; bkj ; 由于是一个三重循环，每个循环从由于是一个三重循环，每个循环从1 1到到n n，则总次数为：，则总次数为： n nn nn=nn=n3 3时间复杂度为时间复杂度为T(n)=O(nT(n)=O(n3 3) )例例 +x; s=0 ;+x; s=0 ; 将将x x自增看成是基本操作，则语句频度为，自增看成是基本操作，则语句频度为，即时间复杂度为即时间复杂度为(1) (1) 。

11、如果将如果将s=0s=0也看成是基本操作，则语句频度为，其时也看成是基本操作，则语句频度为，其时间复杂度仍为间复杂度仍为(1)(1)，即常量阶。，即常量阶。例例 for(i=1; i=n; +i)for(i=1; i=n; +i) +x; s+=x ; +x; s+=x ; 语句频度为：语句频度为：2n2n，其时间复杂度为：，其时间复杂度为：O(n) O(n) ，即为线性，即为线性阶。阶。例例 for(i=1; i=n; +i)for(i=1; i=n; +i)for(j=1; j=n; +j)for(j=1; j=n; +j) +x; s+=x ; +x; s+=x ; 语句频度为：语句频度

12、为：2n2n2 2 ，其时间复杂度为：，其时间复杂度为：O(nO(n2 2) ) ，即为，即为平方阶。平方阶。 定理定理：若若A(n)=a A(n)=a m m n n m m +a +a m-1m-1 n n m-1m-1 +a +a1 1n+an+a0 0是一个是一个m m次多项式，则次多项式，则A(n)=O(nA(n)=O(n m m) )例例 for(i=2;i=n;+i)for(i=2;i=n;+i) for(j=2;j=i-1;+j) for(j=2;j=i-1;+j) +x; ai,j=x; +x; ai,j=x; 语句频度为：语句频度为： 1+2+3+1+2+3+n-2=(1+

13、n-2) +n-2=(1+n-2) (n-2)/2(n-2)/2 =(n-1)(n-2)/2 =n=(n-1)(n-2)/2 =n2 2-3n+2-3n+2 时间复杂度为时间复杂度为O(nO(n2 2) )，即此算法的时间复杂度为平方，即此算法的时间复杂度为平方阶。阶。 一个算法时间为一个算法时间为O(1)O(1)的算法，它的基本运算执行的算法，它的基本运算执行的次数是固定的。因此，总的时间由一个常数（即的次数是固定的。因此，总的时间由一个常数（即零次多项式）来限界。而一个时间为零次多项式）来限界。而一个时间为O(nO(n2 2) )的算法则的算法则由一个二次多项式来限界。由一个二次多项式来限

14、界。 以下六种计算算法时间的多项式是最常用的。以下六种计算算法时间的多项式是最常用的。其关系为：其关系为： O(1)O(O(1)O(n)O(n)O(nn)O(n)O(nn)O(nn)O(n2 2)O(n)O(n3 3) ) 指数时间的关系为：指数时间的关系为： O(2O(2n n)O(n!)O(n)O(n!)O(nn n) ) 当当n n取得很大时，指数时间算法和多项式时取得很大时，指数时间算法和多项式时间算法在所需时间上非常悬殊。因此，只要有人能将间算法在所需时间上非常悬殊。因此，只要有人能将现有指数时间算法中的任何一个算法化简为多项式时现有指数时间算法中的任何一个算法化简为多项式时间算法，

15、那就取得了一个伟大的成就。间算法，那就取得了一个伟大的成就。 有的情况下，算法中基本操作重复执行的次数有的情况下，算法中基本操作重复执行的次数还随问题的输入数据集不同而不同。还随问题的输入数据集不同而不同。例例1 1：素数的判断算法。素数的判断算法。Void prime( int n)Void prime( int n)/ /* * n n是一个正整数是一个正整数 * */ / int i=2 ; int i=2 ; while ( (n% i)!=0 & iwhile ( (n% i)!=0 & i* *1.0 sqrt(n) ) 1.0sqrt(n) )1.0sqrt(n)

16、 )printf(“&d printf(“&d 是一个素数是一个素数n” , n) ;n” , n) ;elseelseprintf(“&d printf(“&d 不是一个素数不是一个素数n” , n) ;n” , n) ; 嵌套的最深层语句是嵌套的最深层语句是i+i+；其频度由条件；其频度由条件( (n% ( (n% i)!=0 & ii)!=0 & i* *1.0 sqrt(n) ) 1.0 sqrt(n) ) 决定，显然决定，显然i i* *1.0 1.01 & change; -i)for (i=n-1; change=TURE;

17、 i1 & change; -i)for (j=0; ji; +j)for (j=0; jaj+1) if (ajaj+1) aj aj+1 ; aj aj+1 ; change=TURE ; change=TURE ; 最好情况：最好情况：0 0次次 最坏情况：最坏情况：1+2+3+1+2+3+ +n-1=n(n-1)/2+n-1=n(n-1)/2 平均时间复杂度为：平均时间复杂度为： O(nO(n2 2) ) 空间复杂度空间复杂度( (Space complexitySpace complexity) ) ：是指算法：是指算法编写成程序后，在计算机中运行时所需存储空间大小编写成程序

18、后，在计算机中运行时所需存储空间大小的度量。记作：的度量。记作： S(n)=O(f(n) S(n)=O(f(n) 其中：其中： n n为问题的规模为问题的规模( (或大小或大小) )该存储空间一般包括三个方面：该存储空间一般包括三个方面： 指令常数变量所占用的存储空间指令常数变量所占用的存储空间; ; 输入数据所占用的存储空间输入数据所占用的存储空间; ; 辅助辅助( (存储存储) )空间。空间。 一般地，算法的一般地，算法的空间复杂度空间复杂度指的是指的是辅助空间辅助空间。 一维数组一维数组anan： 空间复杂度空间复杂度 O(n)O(n) 二维数组二维数组anmanm： 空间复杂度空间复杂

19、度 O(nO(n* *m)m)1.3.4 算法的空间分析算法的空间分析例，有若干学生数据（学生数小于例，有若干学生数据（学生数小于50），），每个学生数据包含学号（每个学生学号是惟每个学生数据包含学号（每个学生学号是惟一的，但学生记录不一定按学号顺序存放）、一的，但学生记录不一定按学号顺序存放）、姓名、班号和若干门课程成绩（每个学生所姓名、班号和若干门课程成绩（每个学生所选课程数目可能不等，但最多不超过选课程数目可能不等，但最多不超过6门）。门）。要求设计一个程序输出每个学生的学号、要求设计一个程序输出每个学生的学号、姓名和平均分以及每门课程（课程编号从姓名和平均分以及每门课程（课程编号从16

20、）的平均分。）的平均分。设计方案设计方案1 1：将学生的全部数据项放在一个：将学生的全部数据项放在一个表中，一个学生的全部数据对应一条记录。由于表中，一个学生的全部数据对应一条记录。由于课程最多可选课程最多可选6 6门，对应的成绩项也应有门，对应的成绩项也应有6 6个。对个。对应的数据结构如下：应的数据结构如下：struct stud int no;/*学号学号*/char name10;/*姓名姓名*/int bno;/*班号班号*/int deg1;/*课程课程1分数分数*/int deg2;/*课程课程2分数分数*/int deg3;/*课程课程3分数分数*/int deg4;/*课程课

21、程4分数分数*/int deg5;/*课程课程5分数分数*/int deg6;/*课程课程6分数分数*/;nonamebnodeg1deg2deg3deg4deg5deg61张斌张斌99017882639285838刘丽刘丽9902659572788079特点：特点：存储空间：中（若学生没有选该课程，对应空间仍存在）存储空间：中（若学生没有选该课程，对应空间仍存在）算法时间：少算法时间：少算法简洁性差：算法完全依赖数据结构算法简洁性差：算法完全依赖数据结构设计方案设计方案2 2：将学生的全部数据项放在一个表：将学生的全部数据项放在一个表中，但一个学生的一门课程成绩对应一条记录。中，但一个学生的

22、一门课程成绩对应一条记录。这样成绩项只需要一个，为了区分不同课程成绩，这样成绩项只需要一个，为了区分不同课程成绩，需增加一个课程编号项。对应的数据结构如下：需增加一个课程编号项。对应的数据结构如下：struct stud int no;/*学号学号*/char name10;/*姓名姓名*/int bno;/*班号班号*/int cno;/*课程编号课程编号*/int deg;/*课程分数课程分数*/;nonamebnocnodeg1张斌张斌99011781张斌张斌99012821张斌张斌99013631张斌张斌99014921张斌张斌99015851张斌张斌99016838刘丽刘丽99021

23、658刘丽刘丽99022958刘丽刘丽99023728刘丽刘丽99024788刘丽刘丽99025808刘丽刘丽9902679特点：特点：存储空间：大存储空间：大算法时间：多算法时间：多算法简洁性：好算法简洁性：好设计方案设计方案3 3：将学生的学号、姓名和班号放：将学生的学号、姓名和班号放在一个表中，将成绩数据放在另一个表中，两者在一个表中，将成绩数据放在另一个表中，两者通过学号关联。前者一个学生对应一个记录，后通过学号关联。前者一个学生对应一个记录，后者一门课程成绩对应一条记录。对应的数据结构者一门课程成绩对应一条记录。对应的数据结构如下：如下：struct stud1 int no;/*学号学号*/char name10;/*姓名姓名*/int bno;/*班号班号*/;struct stud2 int no;/*学号学号*/int cno;/*课程编号课程编号*/int deg;/*分数分数*/;nonamebno1张斌张斌99018刘丽刘丽9902no