计算机算法设计与分析：第一章 概论与相关知识回顾

1、The design and analysis of computer algorithms计算机算法设计与分析计算机算法设计与分析 教学目的教学目的 通过对计算机算法系统的学习与研究，掌握算法设计的主要策略和方法，培养学生对算法的正确性证明以及计算复杂性正确分析的能力，为独立设计算法和对算法进行复杂性分析奠定坚实的理论基础。 主要教学参考书余祥宣，崔国华，邹海明，计算机算法基础 （第三版），2006 ，华中科技大学出版社E.Horowitz and S. Sahni: Fundamentals of Computer Algorithms, Computer Science Press, P

2、itman, Inc. Clifford A. Shaffer, A Practical Introduction to Data Structures and Algorithm Analysis（Second Edition）, Prentice Hall,. 数数据结构与结构与算法分析(C+版) (第二版 英文原版)，电子工业出版社，2002。Sara Baase，Allen Van Gelder，Computer AlgorithmsIntroduction to Design and Analysis （Third Edition）, Addison Wesley Longman，2

3、000，高等教育出版社（影印版），2001年Donald E. Knuth，The Art of Computer Programming（Vol. 1 Fundamental Algorithms， Third Edition），Addison-Wesley，1998，清华大学出版社（英文影印版），2002年Sartaj Sahni，Data Structures，Algorithms，and Applications in C+，McGraw-Hill，1998，机械工业出版社（影印版）1999年苏德富，钟诚， 计算机算法设计与分析，电子工业出版社，2001卢开澄，计算机算法导引设计与分析

4、，清华大学出版社，2001王晓东，计算机算法设计与分析，电子工业出版社2001第一章 概论与相关知识回顾 1.1 算法的概念 形式的定义：形式的定义： 任何一个对所有有效输入总要停机的图灵任何一个对所有有效输入总要停机的图灵机是一个算法。机是一个算法。 非形式的定义：一组有穷的规则，规定了解决某一特定类非形式的定义：一组有穷的规则，规定了解决某一特定类型问题的一系列运算。型问题的一系列运算。/ /有限指令的集合，遵循它可以完成一有限指令的集合，遵循它可以完成一个特定的任务。（个特定的任务。（p21p21）。 算法必须满足以下五条特性：算法必须满足以下五条特性： 1.有限（穷穷）性：算法必须须在

5、有限步内终内终止。 （过过程与与算法的区别区别，如os） 2.确定性：指令必须清须清楚，无二义义性。 (例：分支语语句，表达达式的副作用) 3.能（可）行性：每条条指令必须须充分基本。 4.输输入（=0）：输输入是算法开开始之前从从外部给给出的量。（狭义概狭义概念） 5.输输出（=1）：输输出是同输输入有特定关关系的信息。（广义概义概念）1.2 算法学习的内容 一、设计 二、表达 三、确认 四、分析 五、测试 一、设计：对一个给定的问题，设计出解算该问题的有效算法。设计一个算法的常用技术是什么？ 现实世界中的问题是由无穷多实例组成，个别实例不能被认为是问题。组成问题的无穷多实例当中的每个实例，

6、均可由问题定义域的某个实体及对实体的提问构成。 如：整数加法问题 实例 x+y a+b 实体 a，b 问题定义域 全体整数偶对 指派 a:=2 ，b:=3 提问 2+3=？ 关于p的 问题p=算法A 解算p 如果把p的任一实例的实体作为算法A的输入，算法A在有限步内总能输出一个关于此实例的正确答案。 若：存在一个算法A可以解算问题P，则称问题P是算法可解的。（即：具备可行性，在有限步内终止。不一定真的可解，受条件和时空限制） 能行性：倒底需要多少步，是否可以接受（由计算复杂性理论给出）二、表达 自然语言，计算机语言，类语言 三、确认 算法正确性证明 四、分析 衡量一个算法的好坏 （绝对、相对、

7、效率、效能、时机） 要完成的任务是建立评价标准和分析手段目前对算法评价的标准： 1、正确性 2、时间工作量 3、空间用量 4、简单性 5、最佳性1、正确性 算法正确性的评价包括两个方面 （1）问题的解法在数学上是正确的 （2）执行算法的指令系列是正确的2、时间工作量 时间工作量的评价应该 （1）给出度量的有效信息，恰当地反映算法的实际执行时间 （2）比较解算同一问题的两个算法之间的效率要求：应与具体的计算机、程序语言、程序员、实现细节无关，足够精确又足够一般。 算法时间工作量的评价通常可从以下几种方式考虑： a.实际执行时间与实际程序描述有关、与机器有关、与执行时的数据输入集有关。 b.执行指

8、令的条数依赖于程序设计语言和程序员风格。 c.指定基本操作，度量基本操作执行次数。基本操作：为分析算法而抽取来的特定操作对被研究问题是基本的，是解算这一问题的关键操作，具有随着输入规模增大而增加（次数）的特征。TIttIttnTiiii)()()(*? n度量信息的表达：（输入规模，不同情况）度量信息的表达：（输入规模，不同情况）设：输入集为设：输入集为 ，I I是是 的任一元素，的任一元素， 是是I I出现出现的概率的概率, , 是输入为是输入为I I时的基本操作（执行次数）时的基本操作（执行次数）计算：计算：平均性态：平均性态： 最坏形态：最坏形态： nDnD)(IP)( t InDIII

9、PnA)( t )()()( t)(InWMAXnDI 例：线性表中查找问题 设L是包含n个元素的一个线性表（n个元素互不相同），对某个指定值x，若x在表中找到它出现的下标位置；如不在表中，返回0。3、空间用量 空间用量依赖于特定环境，也可以仅仅通过算法本身考察 空间用量=指令空间+输入数据空间+执行时数据空间 指令空间：与环境相关不可预测且与算法无关，不予考虑 输入数据空间：分为输入按自然形式存储和采用特殊结构 结论： 当输入按自然形式存储时空间用量只计算执行时数据空间 当输入采用特殊结构时空间用量为输入数据空间+执行时数据空间4、简单性：清晰、易读、易懂、易证明 5、最佳性：在同一算法类的

10、算法中作评价，有一个算法对解算问题在这个算法类中是最好的吗？ 同一算法类的算法指解算问题使用同一种基本操作。 定义：为解决某问题P的一个特定算法类（最坏或平均）的计算复杂性为MinTA(n),其中TA(n）为该算法类中任一算法A的（最坏或平均）时间复杂度。 计算复杂性受限于算法类。称对问题P在算法类下的固有复杂度，用CP(n)表示。-很难计算。算法最佳性评判的通常作法：确定算法类 。解决“下界问题” 构造一个函数 f(n)，使得可以证明对算法类中算法A，均有 TA（n）= f(n)成立。则可得f(n)是CP(n)的一个下界。解决“上界问题” 设计出一个算法类中算法A，分析复杂度TA（n），则

11、CP(n)=n0时有TA*（n）=1,n-1 0 如果如果g(n)= O( f(n) ) 则则 O(f(n) + O(g(n) O(f(n) 书中定理2.1的证明 p25 常用的整数求和公式 p271.4 描述算法的语言SPARKS 语言：语法、语义、语用 SPARKS语法 1、基本字符集 （未定义） 2、词法- 保留字、自定义字 数 - 十进制 量 - 常量- false、true |- 变量（属性）-名 | |-类型-标准 | | |-构造 | |-运算 | |-生存周期 | |-作用域全局、局部、形式 |-表达式-|-运算符（算数、关系、逻辑） |-计算顺序 |-类型转化规则 3、语句-

12、赋值 变量-表达式 |-顺序 ； |-分支 |-if-then-else-endif | |-case-endcase | |-goto labal （exit、cycle） |-循环 |-while cond dorepeat | |-loopuntil cond repeat | |-for to by do -repeat | |-loop-repeat |-输入、输出-|-read（参数表） | |-print（参数表） |-注释-/ 4、子结构过程-|-procedure（参数表） |-调用（过程式、函数式） |-返回 return（参数表） |-参数传递方式、纯过程 1.5 基本数

13、据结构回顾 一、线性表 （顺序表、栈、队列、数组、集合） 二、树 （定义、存储、森林、集合的树形表示） 三、二叉树（定义、存储、特殊二叉树、性质、堆、二叉检索树） 四、图1.6 数学知识回顾 一、数学归纳法 数学归纳法基本步骤： 设P(n)是关于整数n的某个命题 给出P(1)为真的证明 给出若P(i) （in-1）为真，则P(n)也为真的证明 结论：命题P(n)对任何整数n都成立 二、双重归纳法 设P(n,m)是与整数m、n有关的命题，证明P(n,m)对任意自然数n、m都成立，步骤如下： 证明命题P(1,m)对任意自然数m成立，命题P(n,1)对任意自然数n成立 假设命题P(n+1,m)和命题

14、P(n,m+1)成立 在条件下证明P(n+1,m+1)成立 由，可知命题P(n,m)对任意自然数，n、m都成立 三、数学归纳法的推广 定义：良序关系 设 是集合S上的一个关系，它满足以下性质： 给定S中的x，y，z。如果xy，yz，则xz 给定S中的x，y，z。以下三种可能恰有一种为真 xy x=y yx 如果A是S的任何非空子集，则A中必有一个元素x，使得对于A中的所有y，x=y， 则称关系为S的一个良序关系。 例：对“小于”关系 正整数 良序 整数 x 正实数 x 定理1（良序关系的等价定义）： 是集合S的一个良序，当且仅当它满足性质和性质，而且对于所有的j1，不存在具有Xj+1Xj的无限

15、序列 X1,X2,X3 。 证明：必要性： 设是S的良序，显然满足。对反证。 如果存在无限序列Xj+1Xj ，则不满足，与定义矛盾。与假设也矛盾。 必要性得证。 充分性：（证在条件下满足） 反证：如果满足不满足 设A是S的一个没有最小元素的非空无限子集，由于A非空，所以在A中可以找到X1，由于A无最小元，故可以找到X2，使X2X1。同理可找到 X3X2 ，X4X3 这样可以在A中找到具有Xj+1Xj (j1)的无限序列X1,X2,X3 与条件矛盾。 所以满足，是S的一个良序。 意义：证明算法的终止性 如果能够把计算的诸状态映射到一个上的良序集S，使得计算的每一步总是从一个状态x进入另一个状态y

16、，并且有f(y)f(x)，则此算法必然终止。 定理2（推广的数学归纳法）： 设S对于为良序集，并且设P(x)是关于S中元素x的一个命题，如果P(x)能在P(y)对于所有的yx为真的假定下得证，则P(x)对S中所有的x为真。 证明： 反证 令A是使得P(x)为假的所有x的集合，若A非空， A对于是良序，于是A中有一个最小元素x0。 而P(y)对所有yx0为真，所以P(x0)为真. 即：不在A中。与假设矛盾。 所以A应为空。 定理得证。 二、递归方程及求解 递归方程：对函数序列，其通项是递归定义的，即其通项h(n)是通过h(0)h(n-1)定义，称为递归式（递归方程） 递归方程常见解法： 1、生成

17、函数法： 对函数序列a0,a1,a2， 函数G(x)=a0+a1x+. 称为序列的生成函数。 生成函数法：首先设对x的某些值生成函数G(x)值收敛，并且能求得G(x)的表达式，然后将G(x)重新展开成x的幂级数，则此展开式中x的n次项的系数即为an的表达式。*对递归式a0,a1,a2，,只是想求an ，x是序列和构造函数的关系桥梁，生成函数G(x)只是形式，G依赖于x，若可以求得G(x)，对参数x是否收敛，收敛域是什么，不必知道。只是想从函数特征中来得到 an 的有用信息。LLnnxaxaaxG10)( 例.Hanoi问题：这是个组合数学中的著名问题。N个圆盘依其半径大小，从下而上套在A柱上。

18、每次只允许取一个移到柱B或C上，而且不允许大盘放在小盘上方。若要求把柱A上的n个盘移到C柱上请设计一种方法来，并估计要移动几个盘次。现在只有A、B、C三根柱子可用。Hanoi塔塔要求：1）每次只能移动一个盘子；2）盘子可以放到ABC任何一个塔座上；3）任何时候，都不能将较大的盘子压在较小的圆盘之上； Hanoi问题是个典型的问题，第一步要设计算法，进而估计它的复杂性，估计工作量。算法：算法：N=2时第一步先把最上面的一个圆盘套在B上z z第二步把下面的一个圆盘移到C上 最后把B上的圆盘移到C上 到此转移完毕A B Cz 对于一般n个圆盘的问题， 假定n-1个盘子的转移算法已经确定。z 先把上面

19、的n-1个圆盘经过C转移到B。z 第二步把A下面一个圆盘移到C上 z 最后再把B上的n-1个圆盘经过A转移到C上 A B CMM 上述算法是递归的运用。n=2时已给出算法；n=3时，第一步便利用算法把上面两个盘移到B上，第二步再把第三个圆盘转移到柱C上；最后把柱B上两个圆盘转移到柱C上。N=4，5，以此类推。 算法分析：算法分析：令h(n)表示n个圆盘所需要的转移盘次。根据算法先把前面n-1个盘子转移到B上；然后把第n个盘子转到C上；最后再一次将B上的n-1个盘子转移到C上。 例例1 1、汉诺塔问题、汉诺塔问题解：构造生成函数 求解求解H(x)H(x) _ 得得1)1(2)(1)1(nhnhh

20、 12)()2() 1 ()(kkxkhxhxhxH 322)2(2) 1 (2)(2)2() 1 ()(xhxhxxHxhxhxHxxxxxxHx 1)()21 (32)1)(21 ()(xxxxH 分解分解H(x)H(x)成幂级数成幂级数 令令 则则 A=-1 B=1A=-1 B=1xBxAxH211)()2 ()2 (21 ()1 (21111)(322 xxxxxxxxH 122) 12() 12() 12() 12(kkknnxxxx12)(nnh 例例2 2（FibonacciFibonacci数列）有一对兔子，假设过两个月便可以繁殖一数列）有一对兔子，假设过两个月便可以繁殖一对兔

21、子，以后每月生一对，问过对兔子，以后每月生一对，问过n n个月后共有多少对兔子？个月后共有多少对兔子？ 解：以为解：以为FnFn系数，构成生成函数系数，构成生成函数 )2(112121nFFFFFnnn 423123221221)()()(xFxFxFxxFxFxxFxFxFxF)251)(251(1)()()()(1 (231232121)2 xxxxxxxFxxFFFxFFxFxFxx 其中其中251251xBxA)511(21A)511(21B 222)()(51)(xxxF251 251 nnnnnnFF)251(51)(51 2、特征方程及特征根法 若a1,a2,ak是常数，且ak0

22、，nk,则递归关系称为K阶常系数线性齐次递归关系，它的特征方程是 可先求出特征方程的根，再由初始条件确定通解表示式中的待定系数，得到原递归关系式的解。knknnnxaxaxax 221102211 kkkkaxaxax(a)(a)如果特征方程有如果特征方程有k k个互不相同的根个互不相同的根q q1 1,q,qk k， 则通解为则通解为 c c1 1,c,ck k为待定系数为待定系数 。nkknnnqcqccqx 221 例：例： 解：递归方程对应的特征方程为：解：递归方程对应的特征方程为： 特征方程的根为特征方程的根为 ： 通解为 32121099210nnnnxxxxxxx09923xxx3, 3, 1321qqqnnnnnncccqcqcqcx) 3(3321332211 初始条件代入初始条件代入 解得： 所以： 2991330321321321ccccccccc121,31,41321ccc43) 1(341111nnnnx （b b）如果特征方程有）如果特征方程有k k个根个根q1,qkq1,qk，其中：，其中： （r r个重根）个重根） 则通解为则通解为 11 riiiqqqnkknirriiiniinnqcqncnccqcqcx )(