算法设计与分析

1、算法设计与分析(3432)2005年9月5日200620日主页： 邮箱：镜像：/(迅腾) /(网易) 1关于本课程课程目的：计算机算法设计与分析导引不是一门试验或程序设计课程也不是一门数学课程教材：计算机算法设计与分析-王晓东授课：徐连诚，87601前导课：数据结构+程序设计授课形式：每周34课时+作业+期中/末考试参考资料：Web资源图书资源2第1章 算法概述本章主要知识点：1.1 算法与程序1.2 算法与数据结构1.3 表达算法的抽象机制1.4 描述算法与算法设计1.5 算法分析的基本原则1.6 算法复杂性分析计划授课时间：34课时31.1算法与程序算法：是满足下述性质的指令序列。输入：有

2、零个或多个外部量作为算法的输入。 输出：算法产生至少一个量作为输出。 确定性：组成算法的每条指令清晰、无歧义。 有限性：算法中每条指令的执行次数有限，执行每条指令的时间也有限。程序：程序是算法用某种程序设计语言的具体实现。程序可以不满足算法的性质(4)即有限性。例如操作系统，是一个在无限循环中执行的程序，因而不是一个算法。操作系统的各种任务可看成是单独的问题，每一个问题由操作系统中的一个子程序通过特定的算法来实现。该子程序得到输出结果后便终止。41.2算法与数据结构描述算法可以有多种方式自然语言方式、表格方式、图示形式等本书将采用C+与自然语言相结合的方式算法与数据结构的关系不了解施加于数据上

3、的算法就无法决定如何构造数据，可以说算法是数据结构的灵魂；反之算法的结构和选择又常常在很大程度上依赖于数据结构，数据结构则是算法的基础。算法数据结构程序51.3表达算法的抽象机制从机器语言到高级语言的抽象高级程序设计语言的主要好处是：高级语言更接近算法语言，易学、易掌握，一般工程技术人员只需 要几周时间的培训就可以胜任程序员的工作；高级语言为程序员提供了结构化程序设计的环境和工具，使得设计出来的程序可读性好，可维护性强，可靠性高；高级语言不依赖于机器语言，与具体的计算机硬件关系不大，因而所写出来的程序可植性好、重用率高；把繁杂琐碎的事务交给编译程序，所以自动化程度高，开发周期短，程序员可以集中

4、时间和精力从事更重要的创造性劳动，提高程序质量。61.3表达算法的抽象机制抽象数据类型抽象数据类型是算法的一个数据模型连同定义在该模型上并作为算法构件的一组运算。抽象数据类型带给算法设计的好处有：算法顶层设计与底层实现分离；算法设计与数据结构设计隔开，允许数据结构自由选择；数据模型和该模型上的运算统一在ADT中，便于空间和时间耗费的折衷；用抽象数据类型表述的算法具有很好的可维护性；算法自然呈现模块化；为自顶向下逐步求精和模块化提供有效途径和工具；算法结构清晰，层次分明，便于算法正确性的证明和复杂性的分析。71.4描述算法与算法设计描述算法可以有多种方式，如自然语言方式、图形表格方式等。在这里，

5、我们将采用C+语言来描述算法。C+语言的优点是类型丰富、语句精炼，具有面向对象和面向过程的双重优点。用C+来描述算法可使整个算法结构紧凑、可读性强。在课程中，有时为了更好地阐明算法的思路，我们还采用C+与自然语言相结合的方式来描述算法。算法设计方法主要有：分治策略、动态规划、贪心算法、回溯法、分支限界、概率算法等，我们将在后面的章节中陆续介绍。81.4描述算法与算法设计问题求解(Problem Solving)证明正确性分析算法设计程序理解问题精确解或近似解选择数据结构算法设计策略设计算法91.5 算法分析的基本原则正确性定义：在给定有效输入后，算法经过有限时间的计算并产生正确的答案，就称算法

6、是正确的。正确性证明的内容：方法的正确性证明算法思路的正确性。证明一系列与算法的工作对象有关的引理、定理以及公式。程序的正确性证明证明所给出的一系列指令确实做了所要求的工作。程序正确性证明的方法：大型程序的正确性证明可以将它分解为小的相互独立的互不相交的模块，分别验证。小模块程序可以使用以下方法验证：数学归纳法、软件形式方法等。101.5 算法分析的基本原则工作量时间复杂性分析计量工作量的标准: 对于给定问题，该算法所执行的基本运算的次数。基本运算的选择：根据问题选择适当的基本运算。问题基本运算在表中查找x比较实矩阵相乘实数乘法排序比较遍历二叉树置指针111.5 算法分析的基本原则占用空间空间

7、复杂性分析两种占用：存储程序和输入数据的空间存储中间结果或操作单元所占用空间额外空间影响空间的主要因素：存储程序的空间一般是常数(和输入规模无关)输入数据空间为输入规模O(n)空间复杂性考虑的是额外空间的大小如果额外空间相对于输入规模是常数，称为原地工作的算法。121.5 算法分析的基本原则简单性含义：算法简单，程序结构简单。好处：容易验证正确性便于程序调试简单的算法效率不一定高。要在保证一定效率的前提下力求得到简单的算法。131.5 算法分析的基本原则最优性含义：指求解某类问题中效率最高的算法 两种最优性最坏情况：设A是解某个问题的算法，如果在解这个问题的算法类中没有其它算法在最坏情况下的时

8、间复杂性比A在最坏情况下的时间复杂性低，则称A是解这个问题在最坏情况下的最优算法。平均情况：设A是解某个问题的算法，如果在解这个问题的算法类中没有其它算法在平均情况下的时间复杂性比A在平均情况下的时间复杂性低，则称A是解这个问题在平均情况下的最优算法。 寻找最优算法的途径 (以最坏情况下的最优性为例)设计算法A，求W(n)。相当于对问题给出最坏情况下的一个上界。寻找函数F(n)，使得对任何算法都存在一个规模为n的输入并且该算法在这个输入下至少要做F(n)次基本运算。 相当于对问题给出最坏情况下所需基本运算次数的一个下界。如果W(n)=F(n)，则A是最优的。如果W(n)F(n)，A不是最优的或

9、者F(n)的下界过低。改进A或设计新算法A使得W(n)F(n)。重复以上两步，最终得到W(n) = F(n)为止。141.5 算法分析的基本原则例：在n个不同的数中找最大的数。基本运算：比较算法：Find Max输入：数组L，项数 n 1 1输出：L中的最大项MAXMAXL(1); i2;while in doif MAX0，存在正数和n0 0使得对所有nn0有：0cg(n)f(n)等价于f(n)/g(n)，as n。f(n)(g(n) g(n)o(f(n)201.6算法复杂性分析渐近分析记号的若干性质（1）传递性：f(n)=(g(n)，g(n)=(h(n) f(n)=(h(n)；f(n)=(

10、g(n)，g(n)=(h(n) f(n)=(h(n)；f(n)=(g(n)，g(n)=(h(n) f(n)=(h(n)；f(n)=(g(n)，g(n)=(h(n) f(n)=(h(n)；f(n)=(g(n)，g(n)=(h(n) f(n)=(h(n)；（2）反身性：f(n)=(f(n)；f(n)=(f(n)；f(n)=(f(n).（3）对称性：f(n)=(g(n) g(n)=(f(n) .（4）互对称性：f(n)=(g(n) g(n)=(f(n) ；f(n)=(g(n) g(n)=(f(n) ；（5）算术运算：(f(n)+(g(n) = (maxf(n),g(n) ；(f(n)+(g(n) =

11、 (f(n)+g(n) ；(f(n)*(g(n) = (f(n)*g(n) ；(cf(n) = (f(n) ；g(n) = (f(n) (f(n)+(g(n) = (f(n) 。211.6算法复杂性分析规则(f(n)+(g(n) = (maxf(n),g(n) 的证明：对于任意f1(n) (f(n) ，存在正常数c1和自然数n1，使得对所有n n1，有f1(n) c1f(n) 。类似地，对于任意g1(n) (g(n)，存在正常数c2和自然数n2，使得对所有n n2，有g1(n) c2g(n) 。令c3=maxc1, c2，n3 =maxn1, n2，h(n)= maxf(n),g(n) 。则对所有的n n3，有f1(n) +g1(n) c1f(n) + c2g(n) c3f(n) + c3g(n)= c3(f(n) + g(n) c32 maxf(n),g(n) 2c3h(n) (maxf(n),g(n).221.6算法复杂性分析取整函数 x ：不大于x的最大整数； x ：不小于x的最小整数。取整函数的若干性质x-1 x x x 0，有： n/a /b = n/ab