1、第一章 算法设计和分析 第一节 概述第二节 算法设计原则第三节 算法复杂性的度量第四节 最优算法第一节 概述一、算法的概念：算法是一系列解决问题的清晰指令，也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出二、算法特性：有穷性、确定性、可行性、有输入、有输出。1.有穷性：对于任意一组合法输入值，在执行有穷步骤之后一定能结束，即：算法中的每个步骤都能在有限时间内完成。2.确定性：对于每种情况下所应执行的操作，在算法中都有确切的规定，使算法的执行者或阅读者都能明确其含义及如何执行。并且在任何条件下，算法都只有一条执行路径。3.可行性：算法中的所有操作都必须足够基本，都可以通过已经实现的基
2、本操作运算有限次实现之。4.有输入：作为算法加工对象的量值，通常体现为算法中的一组变量。有些输入量需要在算法执行过程中输入，而有的算法表面上可以没有输入，实际上已被嵌入算法之中。5.有输出：它是一组与“输入”有确定关系的量值，是算法进行信息加工后得到的结果，这种确定关系即为算法的功能。三、算法的几个要点：1.算法的每一个步骤都必须清晰、明确。2.算法所处理的输入的值域必须仔细定义。nExample求两个正整数m,n的最大公约数gcd(m,n)gcd(m,n)1.1.同一个算法有不同的表达方式：同一个算法有不同的表达方式：（1 1）gcd(m,n)gcd(m,n)的欧几里得算法 第一步：如果n=
3、0，返回m的值作 为结果，结束；否则进入第二步第二步：用n去除m，将余数赋给r。第三步：将n的值赋给m，将r的值 赋给n，回第一步。（2 2）算法Euclid(m,n)/使用欧几里得算法计算gcd(m,n)/输入：两个不全为0的非负整数m,n/输出：m，n的最大公约数While n!=0 dor m mod nm nn rReturn m算法问题求解的过程：算法问题求解的过程： 理解问题决定：计算方法。精确和近似的解法。设计算法正确性证明分析算法根据算法写代码选择精确解和近似解： 用我们日常生活中的自然语言（可以是中文形式， 也可以是英文形式）也可以描述算法。我们可以用数学语言或约定的符号语言
4、来描述算法。一个算法可以用流程图的方式来描述，输入输出、判 断、处理分别用不同的框图表示，用箭头表示流程的流 向。这是一种描述算法的较好方法，目前在一些高级语 言程序设计中仍然采用。也有其他的图形辅助工具。证明算法的正确性分析算法： 算法有两种效率：时间效率和空间效率。 算法的另外两个特性：简单性和一般性。算法和程序的关系：算法和程序的关系：（1）算法着重体现思路和方法，程序着重体现计算机的实现。（2）程序不一定满足有穷性（死循环），另外，程序中的指令 必须是机器可执行的，算法中的指令无此限制。（3）一个算法若用计算机语言来书写，它就可以是一个程序。第二节 算法设计原则第三节 算法复杂性的度量
5、 一个特定算法的“运行工作量”的大小，只依赖于问题的规模（通常用整数量n表示），或者说，它是问题规模的函数。 时间复杂度：假如，随着问题规模 n 的增长，算法执行时算法执行时间的增长率和间的增长率和f(n)f(n)的增长率相同的增长率相同，则可记作：T(n)=O(f(n)T(n)=O(f(n)称称T(n)T(n)为算法的为算法的(渐近)时间复杂度。时间复杂度。第三节 算法复杂性的度量如何估算算法的时间复杂度？如何估算算法的时间复杂度？算法算法 = = 控制结构控制结构( (顺序、分支和循环三种 ) + ) + 原操作原操作（固有数据类型的操作）算法的执行时间算法的执行时间 =原操作原操作(i)
6、(i)的执行次数的执行次数原操作原操作(i)(i)的执行时间的执行时间算法的执行时间算法的执行时间 与与 原操作执行次数之和原操作执行次数之和 成正比成正比 从算法中选取一种对于所研究的问题来说是 基本操作基本操作 的原操作，以该基本操作 在算法中重复执行的次数在算法中重复执行的次数 作为算法运行时间的衡量准则。第三节 算法复杂性的度量算法效率的主要指标是基本操作次数的增长次数。第三节 算法复杂性的度量为了对这些增长次数进行比较和归类，计算机科学家们使用了3种符号：O（读“O”）：上界 （读”omega”）：下界 （读”theta”）：相等1.1.符号符号O O定义1 对于足够大的n，t(n)
7、的上界由g(n)的常数倍来确定， 即：记为t(n) O(g(n) t(n) cg(n)，c为常数 n O(n) 100n+5 O(n) n(n-1)/2 O(n)第三节 算法复杂性的度量2.2.符号符号定义:对于足够大的n，t(n)的下界由g(n)的常数倍来确定， 即：记为t(n) (g(n) t(n) cg(n)，c为常数 n(n) n(n+1)(n) 4n+5 (n)第三节 算法复杂性的度量符号定义:对于足够大的n，t(n)的上界和下界由g(n)的常数倍来确 定，即：c1g(n) t(n) c2g(n)，c1,c2为常数 记为 t(n) (g(n) n+3n+2 (n)n(n-1)/2 (
8、n)4n+5 (n)第三节 算法复杂性的度量利用极限比较增长次数利用极限比较增长次数前两种情况意味着t(n) O(g(n)后两种情况意味着t(n) (g(n)第二种情况意味着t(n) (g(n)第三节 算法复杂性的度量基本的效率类型基本的效率类型 指数时间算法一般有： O( )O(n!)O( )。常量(1)、对数(logn)、线性(n)、平方(n)、立方(n)、指数(2n )、阶乘(n!)其中有六种多项式时间算法最为常见，其关系为：O(1)O(logn)O(n)O(nlogn)O(n2)O(n3)；n2n2nn第三节 算法复杂性的度量void void mult(intint a, intin
9、t b, int&int& c ) / 以二维数组存储矩阵元素，c 为 a 和 b 的乘积 forfor (i=1; i=n; +i) forfor (j=1; j=n; +j) ci,j = 0; forfor (k=1; k=n; +k) ci,j += ai,k* *bk,j; 基本操作: 乘法乘法操作 时间复杂度: O(nO(n ) )例例一一两两个个矩矩阵阵相相乘乘第三节 算法复杂性的度量voidvoid select_sort(int&int& a, intint n) / 将将 a a 中整数序列重新排列成自小至大有序的整数序列中整数序列重新排列成自小至大有序的整数序列。 for
10、 for ( i = 0; i n-1; +i ) j = i; / 选择第选择第 i i 个最小元素个最小元素 forfor ( k = i+1; k n; +k ) if if (ak aj ) j = k; if if ( j !=!= i ) aj ai 基本操作: 比较比较(数据元素)操作操作 时间复杂度: O(n)O(n)例例二二选选择择排排序序空间复杂度空间复杂度：算法在运行过程中临时占用的存储空间的大小被定义为算法的空间复杂性。空间复杂性包括程序中的变量、过程或函数中的局部变量等所占用的存储空间以及系统为了实现递归所使用的堆栈两部分。算法的空间复杂性一般也以数量级的形式给出。S(n) = O(g(n)表示随着问题规模 n 的增大，算法运行所需存储量的增长率与 g(n) 的增长率相同。第三节 算法复杂性的度量第四节 最优算法算法的最优、最差和平均效率算法的最优、最差和平均效率 1.最差效率是指在输入规模为n时，算法在最坏情况下的效率。2.最优效率是指在输入规模为n时，算法在最优情况下的效率。3.平均效率是指在“典型”或“随机”输入的情况下，算法具有的行为（效率）。4.摊销效率是指对于同样的数据结构执行多次操作，然后分摊到每一次上。第四节 最优算法第四节 最优算法
