计算机算法设计与分析：第1章 导 引

1、 计算机算法设计算机算法设计与分析计与分析2.1 算算 法法 一、算法的概念一、算法的概念(I)数值计算数值计算求解数值问题，插值计算、数值积分等求解数值问题，插值计算、数值积分等非数值计算非数值计算 求解非数值问题，主要进行判断比较求解非数值问题，主要进行判断比较算法算法(II) Knuth：算法就是一组有穷的算法就是一组有穷的规则规则,它规定它规定了解决某一特定类型问题的一系列了解决某一特定类型问题的一系列运算运算。 p算法早于计算机出现算法早于计算机出现二、算法的五个重要特性二、算法的五个重要特性 算法算法(Algorithm)确定性确定性 每一种运算必须要有确切的定义，无二每一种运算必

2、须要有确切的定义，无二 义性义性能行性能行性 运算都是基本运算，原则上能在有限运算都是基本运算，原则上能在有限 时间内完成时间内完成输入输入 有有0个或多个输入个或多个输入输出输出 一个或多个输出一个或多个输出有穷性有穷性 在执行了有穷步运算后终止在执行了有穷步运算后终止pNotes：仅仅有穷还不够，还要在现代计算机上：仅仅有穷还不够，还要在现代计算机上有效有效才行才行程序程序( (Program)()(计算过程计算过程) ) 程序是算法用某种程序设计语言的具体实现。程序是算法用某种程序设计语言的具体实现。 程序可以不满足算法的性质程序可以不满足算法的性质(5)有穷性。有穷性。 例如操作系统，

3、是一个在无限循环中执行的程序，因而不是例如操作系统，是一个在无限循环中执行的程序，因而不是一个算法。一个算法。 操作系统的各种任务可看成是单独的问题，每一个问题由操操作系统的各种任务可看成是单独的问题，每一个问题由操作系统中的一个子程序通过特定的算法来实现。该子程序得作系统中的一个子程序通过特定的算法来实现。该子程序得到输出结果后便终止。到输出结果后便终止。程序程序 = 算法算法 + 数据结构数据结构 (By Wirth )p设计设计、确认确认、分析分析、编码、检查、调试、计时、编码、检查、调试、计时证明正确性证明正确性分析算法分析算法理解问题理解问题精确解或近似解精确解或近似解算法设计策略算

4、法设计策略选择数据结构选择数据结构设计算法设计算法设计程序设计程序三、算法学习的五个内容三、算法学习的五个内容如何设计算法如何设计算法运用一些基本设计策略规划算法运用一些基本设计策略规划算法如何表示算法如何表示算法用恰当的方式表示算法用恰当的方式表示算法如何确认算法如何确认算法算法正确性的证明算法正确性的证明(算法确认算法确认algorithm validation)如何分析算法如何分析算法通过时间和空间复杂度的分析，确定算法的优劣通过时间和空间复杂度的分析，确定算法的优劣如何测试程序如何测试程序测试程序是否会产生错误的结果测试程序是否会产生错误的结果设计高效算法SPARKS 语言语言穷举、数

5、学归纳法、反证穷举、数学归纳法、反证法、构造性证明、测试法、构造性证明、测试目的是比较和改进算法目的是比较和改进算法调试和时空分布图调试和时空分布图一、如何分析算法一、如何分析算法 分析算法的目的分析算法的目的设计更高效的算法设计更高效的算法 算法分析的前提算法分析的前提 要求独立于具体的软硬件环境单纯分析算法要求独立于具体的软硬件环境单纯分析算法一台通用计算机一台通用计算机(理想情况下理想情况下)顺序处理、每次一条指令、存储容量足够大、顺序处理、每次一条指令、存储容量足够大、存取时间恒定存取时间恒定 算法分析是对一个算法需要多少计算时间和存储算法分析是对一个算法需要多少计算时间和存储 空间作

6、定量的分析。空间作定量的分析。2.2 分分 析析 算算 法法2.2 分分 析析 算算 法法 一、如何分析算法一、如何分析算法算法分析的准备：算法分析的准备：首先确定使用哪些运算以及执行这些运算所用首先确定使用哪些运算以及执行这些运算所用的时间。的时间。(运算包括基本运算和由一些更基本的运算包括基本运算和由一些更基本的任意长序列的运算所组成的复杂运算任意长序列的运算所组成的复杂运算)其次是要确定出能反映算法在各种情况下工作其次是要确定出能反映算法在各种情况下工作的数据集。的数据集。(即要求我们编造出能产生最好、最即要求我们编造出能产生最好、最坏和有代表性情况的数据配置，通过使用这些坏和有代表性情

7、况的数据配置，通过使用这些数据来运行算法，以更了解算法的性能数据来运行算法，以更了解算法的性能) 二、全面分析算法的两个阶段二、全面分析算法的两个阶段事前分析事前分析(a prior analysis)求出该算法的一个求出该算法的一个时间限界函数时间限界函数(一些关于参数的函数一些关于参数的函数)事前分析只限于每条语句的事前分析只限于每条语句的频率计数频率计数(frequency count).语句的执行次数，与所用的机器无关，且独立于程序设语句的执行次数，与所用的机器无关，且独立于程序设计语言，可由算法直接确定计语言，可由算法直接确定事后测试事后测试(a posterior testing)

8、 收集此算法的实际执行时间和占用空间的统计资料收集此算法的实际执行时间和占用空间的统计资料2.2 分分 析析 算算 法法例：计算语句例：计算语句xx+y在下面三个程序段中的频率计数在下面三个程序段中的频率计数beginxx+yendFC:1beginfor i1 to n doxx+yendFC:nbeginfor i1 to n do for j1 to n doxx+yendFC:n2语句的数量级是指执行它的频率计数之和语句的数量级是指执行它的频率计数之和算法的数量级是指算法的所有语句的频率计数之和算法的数量级是指算法的所有语句的频率计数之和 确定一个算法的数量级十分重要，因为它在本质上反

9、映确定一个算法的数量级十分重要，因为它在本质上反映了算法所需的计算时间。准确分析出一个算法的计算时间有了算法所需的计算时间。准确分析出一个算法的计算时间有时是很困难的，因此我们对算法的计算时间进行渐进表示。时是很困难的，因此我们对算法的计算时间进行渐进表示。2.2 分分 析析 算算 法法算法复杂性分析形式化表述算法复杂性分析形式化表述算法复杂性即算法所需要的计算机资源算法复杂性即算法所需要的计算机资源算法的时间复杂性算法的时间复杂性T(n)；算法的空间复杂性算法的空间复杂性S(n)。其中其中n是问题的规模（输入大小）。是问题的规模（输入大小）。算法的时间复杂性算法的时间复杂性（1）最坏情况最坏

10、情况下的时间复杂性下的时间复杂性 Tmax(n) = max T(I) | size(I)=n （2）最好情况最好情况下的时间复杂性下的时间复杂性 Tmin(n) = min T(I) | size(I)=n （3）平均情况平均情况下的时间复杂性下的时间复杂性 Tavg(n) = 其中其中I是问题规模为是问题规模为n的实例，的实例，p(I)是实例是实例I出现的概率。出现的概率。()( )( )size Inp I T I2.2 分分 析析 算算 法法 f(n)表示算法的计算时间，表示算法的计算时间，n是输入或输出量，是输入或输出量， g(n)是在是在事前分析中确定的某个形式的简单函数，事前分析

11、中确定的某个形式的简单函数，f(n)与机器和语言与机器和语言有关，有关， 而而g(n)是独立于机器和语言的是独立于机器和语言的。 一个算法具有一个算法具有O(g(n)的计算时间是指如果这个算法用的计算时间是指如果这个算法用n值不变的同一类数据在某台机器上运行时，所用的时间值不变的同一类数据在某台机器上运行时，所用的时间总是小于总是小于|g(n)|的一个常数倍。的一个常数倍。 g(n)是计算时间是计算时间f(n)的一个上界函数，的一个上界函数，f(n)的数量级就的数量级就是是g(n) 。 定理定理1.1表明，变量表明，变量n的最高阶数为的最高阶数为m的任一多项式，的任一多项式，与与nm同阶。同阶

12、。 因此一个计算时间为因此一个计算时间为m阶多项式的算法，其时间阶多项式的算法，其时间 都可以用都可以用O(nm)来表示。来表示。 若一个算法有数量级为若一个算法有数量级为c1nm1，c2nm2， cknmk的的 k个语句，则算法的数量级及计算时间就是个语句，则算法的数量级及计算时间就是 c1nm1+c2nm2+cknmk=O(nm) 其中其中 m=maxmi|1 i k(polynomial time algorithm): 用多项式来对其计算时间限界的算法用多项式来对其计算时间限界的算法O(1)O(logn)O(n)O(nlogn)O(n2)O(n3)(exponential time a

13、lgorithm): 计算时间用指数函数限界的算法计算时间用指数函数限界的算法 O(2n)O(n!)1和自然数和自然数n1， 使得对所有使得对所有 n n1，有，有f1(n) c1f(n) 。类似地，对于任意类似地，对于任意g1(n) = O(g(n) ，存在正常数，存在正常数c21和自然数和自然数n2， 使得对所有使得对所有n n2，有，有g1(n) c2g(n) 。令令c3=c1*c2， n3 =maxn1, n2，h(n)= f(n)*g(n) 。则对所有的则对所有的 n n3，有，有 O(f(n)*O(g(n) = f1(n) *g1(n) c1f(n) * c2g(n) = c3f(

14、n)*g(n) = c3h(n) = O(f(n)*g(n) .1 i n1(n) 21(1)/ 2()i nin nn 231(1)(21)/6()i nn nnin 111()12kkkki nknnin 低次项lim0bnnna23012!3!ixixxxexi lim1nxnxen logbaababbaloglog ()loglogcccababloglognbbanalogloglogcbcaablog (1/ )logbbaa1loglogbaabloglogbbcaac|x| 1 for x -1,for any a 0, , logbn = o(na)2345ln(1).23

15、45xxxxxxln(1)1xxxxloglogloglimlim0(2 )bbanannnnn10!(1)!0nnn nn! 1 2 3nn 1!21nnnnen!2nnnnnee1112112nnn!()nno n!(2 )nnlog( !)( log )nnn SPARKS语言的基本数据类型：语言的基本数据类型： 整型整型(integer), 实型实型(real), 布尔型布尔型(boolean), 字符型字符型(char) SPARKS语言的语言的变量命名规则变量命名规则： 以字母开头，不允许使用特殊字符，不允许与保留字重复以字母开头，不允许使用特殊字符，不允许与保留字重复 赋值语句：

16、赋值语句：变量变量 表达式表达式 逻辑运算符：逻辑运算符：and , or , not 关系运算符：关系运算符： ， ， ， ， ， 布尔值布尔值: true，false 数组：任意整数下界和上界的多维数组数组：任意整数下界和上界的多维数组 integer A(l1:u1, , ln:un);例例: integer x, y; char ch;例例: integer A(1:10); real B(3:6 , 1:4); SPARKS语言的条件语句语言的条件语句if 条件条件 then s1 endifif 条件条件 then s1 else s2 endifcase : 条件条件 1: s1

17、 : 条件条件 n: sn : else : sn+1endcase SPARKS语言的语言的case语句语句 SPARKS语言的循环语句语言的循环语句while 条件条件 do Srepeatloop Suntil 条件条件 repeatfor 变量变量初值初值 to 终值终值 by 变量增值变量增值 do Srepeat exit 转到含有转到含有exit的最内层循环语句后面的第一条语句的最内层循环语句后面的第一条语句 goto 标号标号 cycle 结束本次循环结束本次循环 return stop SPARKS语言的函数语言的函数(过程过程)procedure NAME() Sreturn()end NAME函数名函数名,通常用大写字母通常用大写字母说明参数的数据类型说明参数的数据类型和函数中使用的变量和函数中使用的变量parameters 形式参数形式参数global 全局变量全局变量local 局部变量局部变量函数的语句部分函数的语句部分 SPARKS语言的输入、输出：语言的输入、输出： read（参数表）；（参数表）；print（参数表）；（参数表