第1章算法概述

1、第一章算法概述2理解算法的概念。理解算法的概念。理解什么是程序，程序与算法的区别和内在理解什么是程序，程序与算法的区别和内在联系。联系。掌握算法的计算复杂性概念。掌握算法的计算复杂性概念。掌握算法渐近复杂性的数学表述。掌握算法渐近复杂性的数学表述。学习要点学习要点:提纲一、算法与程序二、算法复杂性分析3提纲一、算法与程序一、算法与程序二、算法复杂性分析4什么是算法(Algorithms)？n算法是指解决问题的方法和过程。n算法是对特定问题求解步骤的一种描述，包含操作的有限规则和操作的有限序列。 n通俗一点讲，算法就是一个解决问题的公式（数学手册上的公式都是经典算法）、规则、思路、方法和步骤。算

2、法可以用自然语言描述，也可以用流程图描述，但最终要用计算机语言编程，上机实现。 5算法的特性6算法是若干指令的有穷序列，满足性质：算法是若干指令的有穷序列，满足性质：n确定性：每条指令的意义都是清晰的，无歧义的； n有限性：每条指令的执行次数和执行时间都是有限的； 如：不允许有诸如“x/0”或“x与1或2相加”之类的运算。因为前者结果不能确定，而后者不能确定两种可能的运算应该执行哪一个。n输入：有零个或多个输入；n输出：至少产生一个量作为输出。如：如果算法中的循环步长为零，运算进入无限循环，这是不允许的。算法要求其执行时间是有限的算法要求其执行时间是有限的 ( (终止性终止性) ) 。程序(P

3、rogram)n程序是算法用某种程序设计语言的具体实现。 n程序是依赖于程序设计语言的，甚至依赖于计算机结构的。n算法是脱离具体的计算机结构和程序设计语言的。7算法与程序的区别与联系 n一个程序不一定满足有限性。例操作系统，只要整个系统不遭破坏，它将永远不会停止，即使没有作业需要处理，它仍处于动态等待中。因此，操作系统不是一个算法。 n程序中的指令必须是机器可执行的，而算法中的指令则无此限制。n算法代表了对问题的解，而程序则是算法在计算机上的特定的实现。一个算法若用程序设计语言来描述，则它就是一个程序. 8问题求解(Problem Solving)9证明正确性分析算法设计程序理解问题精确解或近

4、似解选择数据结构算法设计策略设计算法10算法程序算法描述：自然语言，流程图，程序设计语言，伪代码用各种算法描述方法所描述的同一算法，该算法的功用是一样的，允许在算法的描述和实现方法上有所不同。本书中采用类C+伪代码语言描述算法。算法描述n人们的生产活动和日常生活离不开算法，都在自觉不自觉地使用算法，例如人们到商店购买物品，会首先确定购买哪些物品，准备好所需的钱，然后确定到哪些商场选购、怎样去商场、行走的路线，若物品的质量好如何处理，对物品不满意又怎样处理，购买物品后做什么等。以上购物的算法是用自然语言描述的，也可以用其他描述方法描述该算法。问题表示n设Input和Output是两个集合。一个问

5、题是一个关系RInputOutput，Input称为问题R的输入集合，Input的每个元素称为R的一个输入，Output称为问题R的输出或结果集合，Output的每个元素称为R的一个结果。n一个算法面向一类一类问题，而不是仅求解问题的一个或几个实例实例。11排序问题n例如，排序（SORT）问题定义如下：12算法示例插入排序算法a a 0,.,n-10,.,n-1 = 5,2,4,6,1,3= 5,2,4,6,1,3a a 0,.,n-10,.,n-1 = = 5 5, ,2 2,4,6,1,3,4,6,1,3a a 0,.,n-10,.,n-1 = = 2,52,5, ,4 4,6,1,3,6

6、,1,3a a 0,.,n-10,.,n-1 = = 2,4,5,2,4,5,6 6,1,3,1,3a a 0,.,n-10,.,n-1 = = 2,4,5,6,2,4,5,6,1 1,3,3a a 0,.,n-10,.,n-1 = = 1,2,4,5,6,1,2,4,5,6,3 3a a 0 0,.,n-1,.,n-1 = 1,2,3,4,5,6= 1,2,3,4,5,613算法的思想：扑克牌游戏算法描述 n从第一个元素开始，该元素可以认为已经被排序 n取出下一个元素，在已经排序的元素序列中从后向前扫描 n如果该元素（已排序）大于新元素，将该元素移到下一位置 n重复步骤3，直到找到已排序的元

7、素小于或者等于新元素的位置 n将新元素插入到该位置中 n重复步骤2 14 插入排序算法15算法的正确性分析n正确的算法：对于每一个输入都最终停止,而且产生正确的输出。n不正确算法： 不停止(在某个输入上) 对所有输入都停止，但对某输入产生不正确结果n近似算法 对所有输入都停止 产生近似正确的解或产生不多的不正确解n算法正确性证明 证明算法对所有输入都停止 证明对每个输入都产生正确结果16调试程序调试程序 程序正确性证明！程序正确性证明！提纲一、算法与程序二、算法复杂性分析二、算法复杂性分析17算法复杂性 同一问题可用不同算法解决，而一个算法的质量优劣将影响到算法乃至程序的效率。算法分析的目的在

8、于选择合适算法和改进算法。一个算法的评价主要从时间复杂度和空间复杂度来考虑。18 算法分析的目的：设计算法设计出复杂性尽可能低的算法选择算法在多种算法中选择其中复杂性最低者算法复杂性分析n算法复杂性 = 算法所需要的计算机资源。所需资源量越多则复杂性越高，反之所需资源量越少则复杂性越低。其中最为重要的是：n时间复杂性T(n)；空间复杂性S(n)。n其中n是问题的规模（输入大小）。示例：示例：一维数组问题的输入大小数组的长度矩阵问题的输入大小=矩阵的维数图论问题的输入大小=图的边数/结点数19决定算法复杂性的因素n算法的复杂性取决于：(1)求解问题的规模；(2)具体的输入数据；(3)算法本身的设

9、计。20若令N、I、和A分别表示问题的规模、具体的输入和算法本身，则C = F(N, I, A)或 C = FA(N, I) = F( N, I)时间复杂性的计算n时间复杂性T(N, I)的计算为： 21n其中：nti为执行抽象计算机的第i种指令一次所需要的时间，这里假定抽象计算机共有k种指令。nei(N, I)为经过统计后得到的执行抽象计算机的第i种指令的次数。 kT(N, I) = ti ei(N, I) i = 1最坏、最好或平均的情况n最坏情况下的时间复杂性 Tmax(n) = max T(I) | size(I)=n n最好情况下的时间复杂性 Tmin(n) = min T(I) |

10、 size(I)=n n平均情况下的时间复杂性 Tavg(n) =n 其中I是问题的规模为n的实例，p(I)是实例I出现的概率。n实践证明，可操作性最好且最有实际价值的是最坏情况下的时间复杂性。nIsizeITIp)()()(22时间复杂性的计算n为了能够较客观的反映出一个算法的效率，在度量一个算法的工作量时，不仅应该与所使用的计算机、程序设计语言以及程序编制者无关，而且还应该与算法实现过程中的许多细节无关。n为此，可以用算法在执行过程中所需基本运算的执行次数来度量算法的工作量。基本运算反映了算法运算的主要特征，因此，用基本运算的次数来度量算法工作量是客观的也是实际可行的，有利于比较同一问题的

11、几种算法的优劣。n例如，在考虑两个矩阵相乘时，可以将两个实数之间的乘法运算作为基本运算.23算法的数量级n观察以下程序段：24(1) x=x+1;若把程序段看成相应算法的主体，则：(1) 语句执行频数为1，算法数量级为1；(2) for(k=1;k=n;k+) x=x+y; y=x+y; s=x+y; (2)每个赋值语句执行频数为n，算法数量级为3n；(3) for(t=1,k=1;k=n;k+) t=t*2; for (j=1;j0，存在正数和n0 0使得对所有n n0有：0 f(n)0，存在正数和n0 0使得对所有n n0有：0 cg(n) f(n) 28渐进分析中函数比较nf(n)= O

12、(g(n) a b;nf(n)= (g(n) a b;nf(n)= (g(n) a = b;nf(n)= o(g(n) a b.29渐近上界记号OnO(g(n) = f(n) | 存在正常数c和n0使得对所有n n0有： 0 f(n) cg(n) 例如：3n-10=O(n); n2+2n+3=O(n2);3logn+loglogn=O(logn); 常数=O(1)n在大在大O符号中包含常数因子和低阶项被认为是不好的。符号中包含常数因子和低阶项被认为是不好的。应该用大应该用大O的最简单形式描述算法的时间复杂性。的最简单形式描述算法的时间复杂性。302022-4-10计算机算法设计与分析31算法的

13、数量级n观察以下程序段：(1) x=x+1;n若把程序段看成相应算法的主体，则：(1) 语句执行频数为1，算法数量级为1；(2) for(k=1;k=n;k+) x=x+y; y=x+y; s=x+y; (2)每个赋值语句执行频数为n，算法数量级为3n；(3) for(t=1,k=1;k=n;k+) t=t*2; for (j=1;j=t;j+) s=s+j; (3)内循环的赋值语句执行频数为2+22+2n=2(2n-1)；时间复杂度为O(1);时间复杂度为O(n);取c=2， 2(2n-1)2* 2n ;时间复杂度为O(2n);练一练：算法复杂度分析例1： temp=i；i=j；j=temp

14、；32 交换i和j的内容以上三条单个语句的执行次数均为1，该算法段的执行时间是一个与问题规模n无关的常数。算法的时间复杂度为常数阶，记作T(n)=(1)。例2： int ArrayMin(int a , int n) min=a0; for (i=1; in; i+) if (aimin) min=ai; return min; 33 求数组最小值 循环体内计算时间*循环次数。如果循环变量与问题规模n有关，则时间复杂度一般为O(n)。例3：嵌套循环情况 (1) x=0；y=0； (2) for(k=1；k=n；k+) (3) x+； (4) for(i=1；i=n；i+) (5) for(j=

15、1；j=n；j+) (6) y+； 该算法段的时间复杂度为T(n)=(n2)。 当有若干个嵌套循环语句时，算法的时间复杂度是由嵌套层数最多的循环语句中最内层语句的执行次数决定的。34例4：嵌套循环情况for(i=1;i=n;+i) for(j=1;j=n;+j) ci,j=0; for(k=0;k=n;+k) ci,j= ci,j+ai,k*bk,j; 35计算矩阵乘法C=A*B该算法时间复杂度为O(n3 )非递归算法的基本法则：n顺序语句： 各语句计算时间相加；nfor / while 循环：循环体内计算时间*循环次数；n嵌套循环： 最深层循环体内计算时间*所有循环次数；nif-else语句

16、： if语句计算时间和else语句计算时间的较大者。3637(1)称为常数级(logn)称为对数级(n)称为线性级(nc c)称为多项式级(cn n)称为指数级(n!)称为阶乘级(n为问题的规模,c为一常量)算法复杂性的一般表示形式低低高高时间复杂性时间复杂性2022-4-10计算机算法设计与分析38常用的算法设计技术n分治法(Divide and Conquer)n动态规划法(Dynamic Programming)n贪心法(Greedy)n回溯法(Backtracking)n分支界限法(Branch and Bound)n这些算法中都使用了递归(Recursion)。2022-4-10计算

17、机算法设计与分析39伪代码n程序员常常被要求以一种常人能够读懂的方式描述算法。n这样的描述不是计算机程序，但比通常的描述更结构化。n它们还便于对数据结构和算法执行高级分析。n这样的描述称为伪代码。2022-4-10计算机算法设计与分析40例如：n从键盘输入整数n，按C语言的键盘输入函数应写为：scanf(“%d”,&n); 可简写为：scanf(n) 或 输入整数n。n要输出整数量a(1),a(2),a(n)，按C语言的输出函数应写为： for(k=1;k=n;k+) printf(“%d”,ak); 可简写为：printf(a1an) 或 输出a(1n)2022-4-10计算机算法设计与分析

18、41伪代码实例n数组最大值问题：在存储n个整数的数组A中找出最大元素。n算法arrayMax的伪代码描述如下： arrayMax(A, n) 输入：存储输入：存储n1个整数的数组个整数的数组A 输出：输出：A中的最大元素中的最大元素 currentMaxA0 for i 1 to n-1 do if currentMaxAi currentMax Ai return currentMax 伪代码比等价的实际软件代码段更简洁，更容易理解和阅读。2022-4-10计算机算法设计与分析42什么是伪代码？n伪代码是自然语言和高级程序设计语言的混合物，它描述数据结构或算法的一般实现的主要实现。n然而，由于伪代码依