第1章算法与程序PPT讲稿.ppt

《第1章算法与程序PPT讲稿.ppt》由会员分享，可在线阅读，更多相关《第1章算法与程序PPT讲稿.ppt（92页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第1章算法与程序第1页，共92页，编辑于2022年，星期日第1章 算法与程序1.1 算法的基本概念 1.2 算法的表示1.3 算法的设计与评价1.4 算法与程序第2页，共92页，编辑于2022年，星期日1.1 算法的基本概念1.1.1 什么是算法1.1.2 算法的基本特性第3页，共92页，编辑于2022年，星期日什么是算法 早在公元前300年左右出现的著名的欧几里德算法，就描述了求解两个整数的最大公因子的解题步骤。要求解的问题描述为：“给定两个正整数m和n，求它们的最大公因子，即能同时整除m和n的最大整数”。欧几里德当时给出的算法如下：以n除m，并令所得余数为r（必有rn）；若r=0，输出结果

2、n，算法结束；否则继续步骤；令m=n和n=r，返回步骤继续进行。第4页，共92页，编辑于2022年，星期日什么是算法（续）由此，我们可以得出这样的结论，算法就是求解问题的方法和步骤。这里的方法和步骤是一组严格定义了运算顺序的规则；每一个规则都是有效的，且是明确的；按此顺序将在有限次数下终止。有关算法（Algorithm）一词的定义不少，但其内涵基本上是一致的。最为著名的定义是计算机科学家D.E.Kunth在其巨著计算机程序的艺术（Art of Computer Program）第一卷中所做的有关描述。其非形式化的定义是：一个算法，就是一个有穷规则的集合，其中之规则定义了一个解决某一特定类型问题

3、的运算序列。第5页，共92页，编辑于2022年，星期日什么是算法（续）算法的形式化定义如下所述：算法是一个四元组，即（Q，I，F）。其中：Q是一个包含子集I和的集合，它表示计算的状态；I表示计算的输入集合；表示计算的输出集合；F表示计算的规则，它是由Q至它自身的函数，且具有自反性，即对任何一个元素q Q，有F(q)=q。第6页，共92页，编辑于2022年，星期日什么是算法（续）一个算法是对于任何的输入元素x，都在有穷步骤内终止的一个计算方法。在算法的形式化定义中，对任何一个元素xI，x均满足性质 x0=x，xk+1=F(xk)，（k0）该性质表示任何一个输入元素x均为一个计算序列，即x0，x1

4、，x2，xk；该序列在第k步结束计算。第7页，共92页，编辑于2022年，星期日1.1 算法的基本概念1.1.1 什么是算法1.1.2 算法的基本特性第8页，共92页，编辑于2022年，星期日算法的基本特性输入（Input）输出（Output）确定性（Definiteness）有穷性（Finiteness）有效性（Effectiveness）第9页，共92页，编辑于2022年，星期日第1章 算法与程序1.1 算法的基本概念 1.2 算法的表示1.3 算法的设计与评价1.4 算法与程序第10页，共92页，编辑于2022年，星期日1.2 算法的表示1.2.1 自然语言表示1.2.2 流程图表示 1

5、.2.3 NS图表示 1.2.4 伪代码表示1.2.5 程序语言表示 第11页，共92页，编辑于2022年，星期日自然语言表示 自然语言即人们日常使用的语言，如汉语、英语、日语、法语、德语等等。使用自然语言描述算法，人们比较容易接受和理解。如前面的欧几里德算法就是用自然语言描述的。然而，自然语言也具有许多缺点，在使用自然语言描述算法时一定要引起注意：自然语言存在着歧义性，容易导致算法的不确定性；自然语言容易冗长，使得描述不够简洁；自然语言的表示形式是顺序的，描述分支选择和转移时不够直观；自然语言与计算机程序设计语言的差别较大，不易转换为程序。第12页，共92页，编辑于2022年，星期日1.2

6、算法的表示1.2.1 自然语言表示1.2.2 流程图表示 1.2.3 NS图表示 1.2.4 伪代码表示1.2.5 程序语言表示 第13页，共92页，编辑于2022年，星期日流程图表示 流程图是描述算法的图形工具，它采用如下所示的一组图形符号来表示算法：起止框，表示算法的开始或结束；只有一个入口或一个出口。输入输出框，表示算法中数据信息的输入和输出；有一个入口和一个出口。判断框，表示条件判断；有一个入口和多个出口。处理框，表示算法中的一个（或一组）运算或处理；有一个入口和一个出口。流程线，表示算法中各步骤之间的次序关系。连接点，表示算法中的连接位置，主要用于同一算法在不同页描述时的接续等情况。

7、注释框，用于对算法中某些操作的注释说明。第14页，共92页，编辑于2022年，星期日流程图表示举例欧几里德算法的流程图描述如图1-1所示 图1-1欧几里德算法的流程图表示noyesmmodnrend读入m,nr=0beginNm,rn输出nm,n为正整数，算法求其最大公因子第15页，共92页，编辑于2022年，星期日流程图表示（续）同自然语言相比，用流程图描述算法直观，可以一目了然；算法步骤间用流程线连接，次序关系清楚，容易理解；可以很方便地表示顺序、选择和循环结构，不依赖于任何计算机和计算机程序设计语言，有利于不同环境下的程序设计。但是，流程图也还存在一些缺点，诸如：不易于表示算法的层次结构

8、；不易于表示数据结构和模块调用关系等重要信息；容易使人过早地考虑算法的控制流程，而忽视算法的全局结构；用流程线代表控制流，控制转移随意性较大。若对流程线的使用不加限制，随着求解问题规模和复杂度的增加，流程图会变得很复杂，使人难以阅读、理解和修改，从而使算法的可靠性难以保证。第16页，共92页，编辑于2022年，星期日1.2 算法的表示1.2.1 自然语言表示1.2.2 流程图表示 1.2.3 NS图表示 1.2.4 伪代码表示1.2.5 程序语言表示 第17页，共92页，编辑于2022年，星期日NS图表示 为了克服传统流程图的缺点，1973年美国学者纳斯（I.Nassi）和施内德曼（B.Shn

9、eiderman）提出了一种表示算法的较好工具N-S图。它独立于任何计算机和计算机语言，又能很方便地转换为计算机语言程序；它去掉了流程线全部用矩形方框来描述，限制了算法流程转移控制的随意性，又节省了篇幅；它很容易表示算法中的嵌套关系和模块中的层次关系，功能域可以从框图中直接反映出来；它仍是图形工具，阅读起来直观、明确、容易理解。第18页，共92页，编辑于2022年，星期日NS图表示（续）N-S图的基本图形符号如下：ABTFPAB当PAA直到P顺序结构，由两个或多个矩形框组成。其中A和B可以是基本操作，也可以是其它基本结构（如选择结构，循环结构）。选择结构，当条件P成立时执行操作A，否则执行操作

10、B。当型循环结构。当条件P成立时反复执行操作A，直到条件P不成立时止。直到型循环结构。反复执行操作A，直到条件P成立时止。第19页，共92页，编辑于2022年，星期日NS图表示举例 由于N-S图象一个多层的盒子，所以也称作盒图。用N-S图表示欧几里德算法如图1-2所示。读入正整数m,n读入正整数m,nm mod nrmr当r0反复做nm,rnnm,rnm mod nrm mod nr直到r=0时止输出最大公因子n输出最大公因子n(a)当型循环结构实现(b)直到型循环结构实现图1-2 欧几里德算法的N-S图表示第20页，共92页，编辑于2022年，星期日1.2 算法的表示1.2.1 自然语言表示

11、1.2.2 流程图表示 1.2.3 NS图表示 1.2.4 伪代码表示1.2.5 程序语言表示 第21页，共92页，编辑于2022年，星期日伪代码表示伪代码是介乎于自然语言和计算机程序语言之间的一种表示算法的工具。它用文字和符号描述问题的求解方法和步骤而不使用图形符号。如同一篇文章自上而下书写，每行写一个基本操作，而用若干行写出一个基本结构。因而书写方便，格式紧凑，清晰易读好理解，也更容易转化为某一计算机程序语言表示的程序。和图形工具相比较，便于修改，但直观性能较弱。第22页，共92页，编辑于2022年，星期日伪代码表示（续）下面，我们给出欧几里德算法的一种伪代码描述如下：Begin(算法开始

12、)Read(m,n)m mod nr while r0 do nm rn m mod nr write(n)End(算法结束)第23页，共92页，编辑于2022年，星期日1.2 算法的表示1.2.1 自然语言表示1.2.2 流程图表示 1.2.3 NS图表示 1.2.4 伪代码表示1.2.5 程序语言表示 第24页，共92页，编辑于2022年，星期日程序语言表示计算机程序设计语言，是计算机能够接受、理解和执行的算法描述工具。计算机不能直接识别自然语言、流程图、N-S图和伪代码等工具描述的算法，而设计算法的目的就是要用计算机来解决问题，算法最终都要用某一具体的计算机程序设计语言来表示。从这个意义

13、上讲，流程图、N-S图和伪代码都仅仅是为了求解问题而设计算法时的辅助工具。为了更好更准确地描述算法，人们使用图形或表格还创造了许多专用的算法设计辅助工具，如PAD图、判定表、数据流图、Warnier-rr图等等。第25页，共92页，编辑于2022年，星期日程序语言表示（续）和自然语言一样，计算机程序设计语言也是串行的描述，很不直观。对于较复杂的问题，人们很难用计算机程序设计语言直接写出程序。所以在算法设计阶段，一般是先采用某个专用的辅助工具来描述算法，在算法设计好之后，再把它转化为某一具体程序设计语言描述的程序。第26页，共92页，编辑于2022年，星期日程序语言表示（续）作为例子，下面我们给

14、出欧几里德算法的C语言描述如下：#include”stdio.h”main()int m,n,r;printf(“请输入两个正整数：”)；scanf(“%d%d”,&m,&n);printf(“n%d和%d的最大公约数是：”，m,n);r=m%n;while(r!=0)m=n;n=r;r=m%n;printf(“%dn”,n);运行结果：请输入两个正整数：56 3256和32的最大公约数是：8 第27页，共92页，编辑于2022年，星期日第1章 算法与程序1.1 算法的基本概念 1.2 算法的表示1.3 算法的设计与评价1.4 算法与程序第28页，共92页，编辑于2022年，星期日1.3 算法

15、的设计与评价1.3.1 评价算法的标准1.3.2 算法的环路复杂度1.3.3 算法的时空效率1.3.4 常见的算法设计方法第29页，共92页，编辑于2022年，星期日评价算法的标准评价一个算法优劣的五条标准：正确性可读性健壮性高效性简洁性一个好的算法是满足这五条标准要求的算法。第30页，共92页，编辑于2022年，星期日评价算法的“正确性”标准所设计出来的算法要能够正确求解给定的问题。这就要求算法中的每一个步骤的描述是准确无歧义的，并且是可以执行的；要求算法能够满足问题要求，并在有限步骤内获得结果；否则就不具备正确性要求，更谈不上解决给定的实际问题了。算法要能经得起一切可能的输入数据的考验。第

16、31页，共92页，编辑于2022年，星期日评价算法的“正确性”标准（续）在将算法用程序语言表示为特定语言的程序后还必须注意：程序中不含有语法错误；对于一切合法的输入数据，程序能够产生满足要求的输出结果；对于一切非法的输入数据，程序能够得出满足规格说明的结果；对于精心选择的，甚至是带有刁难性的典型测试数据，程序都有满足要求的输出结果。第32页，共92页，编辑于2022年，星期日评价算法的“可读性”标准表示出来的算法要能够方便地供人们阅读、理解和交流。算法的可读性好是保证正确性的前提，良好的可读性有利于人们理解算法思想，减少出错机会，便于检查和修改。可适当地增加注释，增强算法或程序的可读性。第33

17、页，共92页，编辑于2022年，星期日评价算法的“健壮性”标准算法对意外情况的反映能力要强。当输入数据非法、0作除数、负数开平方等，算法应能做出相应的处理，给出错误信息或终止算法执行，避免产生错误的或莫明其妙的输出结果。第34页，共92页，编辑于2022年，星期日评价算法的“高效性”标准算法的执行效率要高。算法的效率可分为时间效率和空间效率。时间效率是通过该算法转化的程序在计算机上运行的时间耗费来确定，在算法设计与分析阶段用执行基本操作的次数（是问题规模的函数）相对于问题规模的渐近阶来表示。空间效率主要考虑除存储数据结构之外的辅助存储空间。一个高效算法是指执行算法耗费时间少，使用辅助存储空间小

18、的算法。第35页，共92页，编辑于2022年，星期日评价算法的“简洁性”标准所设计出来的算法要尽可能地简洁。对于同一问题所设计的不同算法，越简洁明了的越好。越简洁的算法可读性越好，越易于理解、编码和调试、测试，越受人们欢迎。第36页，共92页，编辑于2022年，星期日评价算法的标准（续）在评价一个算法时，要对这五个方面综合考虑，不要片面追求某一指标。有些指标之间往往是相互制约的，如时间效率与空间效率，简洁性与高效性等等；要学会针对具体问题要求和软硬件实现环境进行综合平衡，设计出满足需要的好算法。第37页，共92页，编辑于2022年，星期日1.3 算法的设计与评价1.3.1 评价算法的标准1.3

19、.2 算法的环路复杂度1.3.3 算法的时空效率1.3.4 常见的算法设计方法第38页，共92页，编辑于2022年，星期日算法的环路复杂度算法的复杂性很大程度上取决于控制流程的复杂性。单一的顺序结构最简单；循环结构和选择结构所构成的环路越多算法就越复杂。基于这一种观点，针对算法的流程图表示，我们先介绍算法的环路复杂度的概念和度量方法。第39页，共92页，编辑于2022年，星期日算法的环路复杂度（续）算法（或程序）的环路复杂度度量方法，以图论为工具，先画出程序图，然后用该程序图的环路作为算法（或程序）复杂性的度量值。所谓程序图可以看成是退化了的流程图，也就是把算法（或程序）流程图中的每个处理框都

20、退化成为一个点，原来连接不同框之间的流程线变成连接不同点的有向弧，这样得到的有向图称之为程序图。程序图是连通图，这是因为从算法流程的入口点总是能够到达图中的任何一个结点；如果我们再增加一条由出口到达入口的虚弧，则从图中任何一个结点出发都可以到达其它所有结点，使得程序图变为强连通的有向图。第40页，共92页，编辑于2022年，星期日算法的环路复杂度举例例如图1-1所示的欧几里德算法的流程图所对应的程序图如图1-3所示。图1-3欧几里德算法流程图的程序图图1-1欧几里德算法的流程图表示noyesmmodnrend读入m,nr=0beginNm,rn输出n第41页，共92页，编辑于2022年，星期日

21、算法的环路复杂度的计算方法强连通图中线性无关的环路个数我们可以用如下的公式确定：V(G)=e-n+p 其中：V(G)是图G中环路的个数；e是图G中有向弧的条数，包括由出口到入口增加的一条虚弧；n是图G中结点的个数；p是图G中连通分量的个数，对于连通图而言p恒为1。第42页，共92页，编辑于2022年，星期日环路复杂度的计算方法举例例1：前述的欧几里德算法的程序图（图1-3）中，有8条有向弧和7个结点，由该公式可以确定其环路复杂度如下：V(G)=8-7+1=2 图1-4程序图的复杂度n例2：如图1-4所示的程序图中，有11条弧和7个结点，由该公式 可如下确定其环路复杂度：V(G)=11-7+1=

22、5第43页，共92页，编辑于2022年，星期日算法的环路复杂度的计算方法（续）除了应用上述的公式法计算之外，还有如下的两种方法可以用来确定程序图的环路复杂度：观察法，即观察强连通的程序图在平面上所围成的独立区域的个数。如图1-3中由有向弧（含虚弧，下同）和结点围成的独立区域有两个，即环路数为2，环路复杂度为2；而图1-4中的独立区域有五个，环路数为5，环路复杂度为5。第44页，共92页，编辑于2022年，星期日算法的环路复杂度的计算方法（续）利用判定语句计算法，即把程序图中所有出现的分支结点处所需要的判定的总个数加起来再加1。每一个分支结点处所需要的判定数为该结点分支数（即出度）减1，即二路分

23、支需要一个判定，三路分支需要两个判定，依此类推。如图1-3中只有一个结点（第四个）是分支结点且为二路分支，故所需要的判定为一个，其环路复杂度（即环路数）为2；而图1-4中有两个结点（上数第二个和左下结点）是分支结点且结点都为三路分支，故所需的判定为2+2=4个，其环路复杂度为5。第45页，共92页，编辑于2022年，星期日算法的环路复杂度（续）算法的环路复杂度越高，说明算法的控制越复杂，在转化为程序时的难度就越大，转化后的程序测试难度也就越大问题越多。在设计算法时，一般地应控制模块的环路复杂度在10以内为宜。环路复杂度的度量方法的最大优点在于它的简明性，只要知道算法中的判定个数即可。然而它也有

24、许多不足之处，如没有区分不同类型控制流的不同复杂性（如选择结构和循环结构之间，嵌套选择结构和多选择结构之间的不同复杂性）等。在评价和度量算法复杂性时，可根据实际需要结合其它方法一块使用。第46页，共92页，编辑于2022年，星期日1.3 算法的设计与评价1.3.1 评价算法的标准1.3.2 算法的环路复杂度1.3.3 算法的时空效率1.3.4 常见的算法设计方法第47页，共92页，编辑于2022年，星期日算法的时空效率如果算法是用N-S图、伪代码、程序语言或其它方式表示的，要度量其环路复杂度需要先把它们的表示转化为流程图表示，然后把流程图退化为程序图再确定其环路数。环路复杂度是一种定量地评价算

25、法复杂度的方法。下面我们再介绍一种适应面更广泛的定性评价算法复杂度的方法，即大O方法。第48页，共92页，编辑于2022年，星期日算法的时空效率（续）执行一个算法的时间代价，是指将该算法转化为程序后在计算机上运行的时间耗费，即算法中每条语句在计算机上执行的时间总和，大致上可以认为它等于计算机执行一种基本操作（如赋值运算、比较运算、移动操作等）所需的时间与算法中进行基本操作总次数的乘积。而每条语句的执行时间则应该是执行该语句一次所需的时间与该语句执行的次数（也称之为频度）的乘积。某条语句执行一次所需的时间一般地是随机器而异的，取决于具体机器的性能、速度和编译代码的质量，是由机器本身的软、硬件环境

26、所决定的，与算法无关。所以，我们可以假设执行每条语句所需的时间均为单位时间。因此，对算法执行时间的讨论就可以转化为对算法中所有语句的执行次数（即频度）的讨论。第49页，共92页，编辑于2022年，星期日大O方法计算举例两个n*n矩阵相乘的算法描述如下：for(i=1;i=n;i+)/*n+1次*/for(j=1;j=n;j+)/*n(n+1)次*/cij=0;/*n2次*/for(k=1;k=n;k+)/*n2(n+1)次*/cij=cij+aik*bkj;/*n3次*/第50页，共92页，编辑于2022年，星期日大O方法计算举例（续）其中，每一条语句的频度说明在注释中。我们把算法所耗费的时间

27、定义为该算法中每条语句的频度之和，则该算法的时间耗费T(n)可表示为T(n)=2n3+3n2+2n+1显然，它是矩阵的阶（该问题的规模）n的函数。并且当n时，T(n)/n32。这表示当n趋于无穷大时，T(n)与n3是同阶函数或者说是同量级的。引入大O记号可记作T(n)=O(n3)第51页，共92页，编辑于2022年，星期日时间复杂度引入大O记号表示的算法的时间耗费T(n)通常称之为算法的时间复杂度，如矩阵相乘算法的时间复杂度为O(n3)。这种时间复杂度的大O表示法，实质上是把算法的基本操作总数表示为问题规模n的函数之后，寻找出当问题规模n趋于无穷大时该函数的同阶最简形式即渐近性态下的同阶最简函

28、数，有时也简称之为渐近阶。问题的规模是指算法中要处理的数据量的规模，通常用一个整型量n来表示。对于求解不同的问题，规模n具有不同的值。第52页，共92页，编辑于2022年，星期日时间复杂度（续）时间复杂性的渐近阶表示，是对算法时间性能优劣的宏观定性评价。例如，为了求解同一问题所设计的两个不同的算法A1和A2，其时间耗费分别为T1(n)=40n2和T2(n)=5n3；显然当问题规模nT2(n)，算法A2比A1时间花费少；利用渐近阶表示的时间复杂度O(n2)和O(n3)反映了对这两个算法时间性能优劣的宏观定性评价结论。由于是宏观的定性评价，算法中频度最大的语句的频度，与算法中每条语句频度的和T(n

29、)是同阶函数；所以人们在计算算法时间复杂度时，往往只需考虑算法中频度最大的语句的频度就可以了。第53页，共92页，编辑于2022年，星期日时间复杂度计算举例例如对于下面的程序段：x=0;for(i=1;in;i+)for(j=1;ji;j+)for(k=1;kj;k+)x+;我们只须关心程序段中执行频度最大的语句最内层循环的循环体语句x+，它的执行次数是由于n3是它的渐近性态下的同阶最简函数，可得上述程序段的时间复杂度为T(n)=O(n3)。第54页，共92页，编辑于2022年，星期日简明实用的程序分析法则 执行一条基本操作如读写或赋值语句等，需要O(1)的时间花费。对于顺序结构，需要执行一系

30、列语句，所用时间用求和准则估计。对于选择结构如if语句，主要时间耗费是执行then子句或else子句所用的时间；此外，检验条件还需用O(1)的时间。多选择结构的时间耗费与if语句类同。对于循环结构，执行时间为多次迭代中循环体的执行和检验循环条件的耗时，常用乘法准则估计。对于复杂算法，可以将它分成几个容易估算的部分分别估计，然后利用求和准则和乘法准则计算整个算法的时间复杂度。第55页，共92页，编辑于2022年，星期日简明实用的程序分析法则（续）大O下的求和准则若T1(m)=O(f(m)，T2(n)=O(g(n)（不相同问题规模时）则T1(m)+T2(n)=O(f(m)+g(n)若T1(n)=O

31、(f(n)，T2(n)=O(g(n)（相同问题规模时）则T1(n)+T2(n)=O(max(f(n),g(n)若g(n)=O(f(n)（特殊运算规则）则O(f(n)+O(g(n)=O(f(n)第56页，共92页，编辑于2022年，星期日简明实用的程序分析法则（续）大O下的乘法准则若T1(m)=O(f(m)，T2(n)=O(g(n)（不相同问题规模时）则T1(m)*T2(n)=O(f(m)*g(n)若T1(n)=O(f(n)，T2(n)=O(g(n)（相同问题规模时）则T1(n)*T2(n)=O(f(n)*g(n)若c是一个正常数（特殊运算规则）则O(cf(n)=O(f(n)第57页，共92页，

32、编辑于2022年，星期日程序分析法则举例如对前述的矩阵相乘算法，它是三层嵌套的循环结构，我们可以从最内层循环的循环体开始分析：是赋值语句，与问题规模无关，时间复杂度为常数阶O(1)，即T5(n)=O(1)；对于第条语句，T4(n)=O(n)，它与第条语句是循环关系应该用乘法准则，即T4(n)*T5(n)=O(1*n)=O(n)；对于第条语句T3(n)=O(1)，它与第、是顺序结构应该用求和准则，即T3(n)+T4(n)*T5(n)=O(max(1,n)=O(n)；第条语句其T2(n)=O(n)，到是它的循环体适用乘法准则，故有T2(n)*(T3(n)+T4(n)*T5(n)=O(n*n)=O(

33、n2)；第条语句的耗时T1(n)=O(n)，到是它的循环体适用乘法准则，所以有T1(n)*(T2(n)*(T3(n)+T4(n)*T5(n)=O(n*n2)=O(n3)。第58页，共92页，编辑于2022年，星期日时间复杂度（续）利用这组程序分析法则可得矩阵相乘算法的时间复杂度为T(n)=O(n3)，它与我们在前面用所有语句执行频度的总和关于问题规模的函数表达后求渐近阶得出的结果一致，但却省去了计算所有语句执行频度总和的麻烦。实际上，算法或程序的执行时间不仅依赖于所求解问题的规模，还与它所处理的数据的状态有关。一般在不做任何说明的情况下，讨论其时间复杂度是指在最坏情况下的时间复杂度，通常可记作

34、Tmax(n)；有时还要讨论其平均情况下的时间复杂度Tavg(n)。第59页，共92页，编辑于2022年，星期日空间复杂度衡量一个算法优劣的另一个因素是空间代价，即执行由算法转化的程序时所占用存储空间的大小。为了执行算法所占用的存储空间包括如下三个方面：为了在计算机上存储程序本身所占用的存储空间。算法或程序中的输入和输出数据所占用的存储空间。算法或程序在执行过程中临时占用的存储空间。这部分空间是与算法本身密切相关的，因算法设计的不同而异，是我们讨论算法的空间代价时所要着重讨论的方面。度量一个算法或程序在执行过程中所花费的额外存储开销（即临时存储工作单元）的大小也是用大O方法，度量的结果称之为算

35、法的空间复杂度。空间复杂度和时间复杂度一样，也是用相对于问题规模函数的渐近阶形式给出，如O(1)、O(n)等。第60页，共92页，编辑于2022年，星期日时（空）间复杂度常见的时间（或空间）复杂度有：常数阶O(1)对数阶O(log2n)线性阶O(n)线性对数阶O(nlog2n)平方阶O(n2)立方阶O(n3)指数阶O(2n)指数阶的算法效率极低，当问题规模n稍大时就无法使用。第61页，共92页，编辑于2022年，星期日1.3 算法的设计与评价1.3.1 评价算法的标准1.3.2 算法的环路复杂度1.3.3 算法的时空效率1.3.4 常见的算法设计方法第62页，共92页，编辑于2022年，星期日

36、常见的算法设计方法为了获得有效的算法，必须了解一些解题的基本思想和方法。对于许多问题，只要仔细分析了数据对象后，相应的处理方法就有了；对于有些问题则不然。然而，作为探寻问题求解思路的基本思想和方法，对于任何算法设计都是有用的。下面我们简要介绍一些常用的算法设计方法和技术：穷举法迭代法递推法递归法回溯法贪婪法分治法第63页，共92页，编辑于2022年，星期日1.穷举法穷举法亦称作枚举法。它的基本思想是：首先根据求解问题的部分条件确定答案的大致范围，即列举出解的所有可能的情况；然后在此范围内对所有可能的情况逐一验证，若某个情况经过验证符合问题条件则为一个解，若全部情况验证后均不符合题目条件则问题无

37、解，从而得出求解问题的完整解。例如要找出200到500之间的所有素数，我们只要对这个范围内的每一个数逐个用素数的定义去判断就行了。穷举法的特点是算法简单，但有时运算量大效率较低。在可以确定解的取值范围，但一时又找不到更好的算法时，就可以使用穷举法求解。第64页，共92页，编辑于2022年，星期日2.迭代法迭代法的基本思想是，由一个量的原值求出它的新值，不断地再用新值替代原值求出它的下一个新值，直到得到满意的解。新值与原值之间存在一定的关系，这种关系可以用一个公式来表示，称之为迭代公式。迭代法主要用于那些很难用或无法用解析法求解的一类计算问题，如高次方程和超越方程等；使得复杂问题的求解过程，转化

38、为相对较简单的迭代算式的重复执行过程，用数值方法求出问题的近似解。第65页，共92页，编辑于2022年，星期日迭代法（续）使用迭代法构造这一类问题求解算法的基本方法是：先确定一个收敛性能好（即收敛速度快）的迭代公式，选取解的一个近似值（即迭代初值）和解的精度要求（即允许的最大误差范围），然后用循环处理实现迭代过程，终止循环的条件是前后两次得到的近似值之差的绝对值小于解的精度要求，并认为最后一次得到的近似解为问题的解。这种迭代方法称作逼近迭代，如著名的牛顿迭代法就是这种逼近迭代方法。此外，精确值的计算也可以使用迭代法。例如计算s=1+2+3+1000，可选取迭代公式s+is和迭代初值0（即0s）

39、。第66页，共92页，编辑于2022年，星期日3.递推法递推法是从前面的一些量推出后面的一些量的一种方法，它从已知的初始条件出发，逐次推出所需要求解的各中间结果和最终结果。递推过程往往表现为迭代，即由一些量的原值推出它的新值，不断地用新值替代原值推出下一个新值，直到推出最终结果，新值与原值之间的关系用递推公式表示。例如Fibonacci数列存在着递推关系 F(1)=1，F(2)=1，F(n)=F(n-1)+F(n-2)(n2)第67页，共92页，编辑于2022年，星期日递推法（续）需要求出Fibonacci数列中某一项的值，利用递推公式逐步求出F(3)，F(4)直到求出该项的值，也许有人会说，

40、如果使用通项公式计算岂不更方便吗？事实上，有些递推问题的通项公式是很难找出的，即使找出通项公式计算也不一定简便。如Fibonacci数列的通项公式为 显而易见，找出这个通项公式不易，利用它计算F(n)也相当费力。相反地，若利用递推初值和递推公式计算F(n)就容易和方便多了。第68页，共92页，编辑于2022年，星期日4.递归法 如果一个过程直接或间接地调用它自身，则称该过程是递归的；直接调用自身称作直接递归，间接调用自身则称作间接递归。递归是构造算法的一种基本方法，它将一个复杂问题归结为若干个较为简单的问题，然后将这些较为简单的问题进一步归结为更简单的问题，这个过程一直进行下去直到归结为最简单

41、的问题时为止。这个最简单的问题即为递归终止条件，也称作递归出口。在高级语言程序设计课程中介绍的著名的汉诺（Hanoi）塔问题的求解算法和后续章节中介绍的有关树和二叉树的许多算法，都是递归法的典型运用。第69页，共92页，编辑于2022年，星期日递归法和递推法比较 递归和递推是既有区别又有联系的两个概念。递推是从已知初始条件出发逐次推出最后所求的值；递归则是从函数本身出发，逐次上溯调用其本身求解过程直到递归出口，然后再从里向外倒推回来得到最终的值。一般地说，一个递推算法总可以转换为一个递归算法。对于同一问题所设计的递归算法往往要比相应的非递归算法（如递推算法）付出更多的执行时间代价和更多的辅助存

42、储空间开销。第70页，共92页，编辑于2022年，星期日递归法和递推法比较（续）然而，利用递归方法分析和设计算法可使难度大幅度降低，且程序设计语言中一般都提供递归机制；利用递归过程描述问题求解算法不仅非常自然，而且算法的正确性证明要比相应的非递归算法容易得多；另外有成熟的方法和技术，可以很方便地把递归算法改写为非递归算法。所以，递归技术是算法设计的基本技术，递归方法是降低分析设计难度提高设计效率的重要手段和工具。第71页，共92页，编辑于2022年，星期日5.回溯法回溯法是算法设计中的一种基本策略，它通过对问题的分析找出一个解决问题的线索，然后沿这个线索逐步试探。对于每一步试探，若成功就继续下

43、一步试探；若不成功就逐步退回换别的路线再进行试探，直至探索成功得到问题的解或试探完所有的线索问题无解。在那些涉及到寻找一组解的问题或者满足某些约束条件的最优解的问题中，许多都可以用回溯法来求解。例如，在国际象棋棋盘上的骑士周游问题和我们平时参加的走迷宫游戏，都是使用回溯法进行的。第72页，共92页，编辑于2022年，星期日6.贪婪法贪婪法也称作贪心算法，它是通过一系列的选择来得到问题的一个解。贪婪法在每一步所做出的选择，都总是在当前状态下看来是最好的选择即贪婪选择，并希望通过每次所作的贪婪选择导致最终结果是求解问题的一个最优解。换句话说，贪婪法并不从整体最优上加以考虑，它做出的选择只是在某种意

44、义上的局部最优选择，但希望算法得到的最终结果也是整体最优的。虽然这种贪婪策略不能对所有问题都得到整体最优解，然而在许多情况下的确能够产生整体最优解。在一些情况下，即使贪婪算法不能得到整体最优解，其最终结果却是最优解的很好近似。第73页，共92页，编辑于2022年，星期日7.分治法求解一个复杂问题时，尽可能地把这个问题分解为若干较小的子问题，在找出各个较小问题的解之后再组合成为整个问题的解，这就是所谓的分治法。使用分治法时，往往要按问题的输入规模来衡量问题的大小；当要求解问题的输入规模相当大时，应选择适当策略将输入划分成若干子集合得到一组子问题，在求出各子问题的解之后用适当的方法把它们合并成整个

45、问题的解，分治法便应用成功了。如果得到的子问题还相对过大，可再次使用分治法将这些子问题进一步划分成更小的子问题。第74页，共92页，编辑于2022年，星期日第1章 算法与程序1.1 算法的基本概念 1.2 算法的表示1.3 算法的设计与评价1.4 算法与程序第75页，共92页，编辑于2022年，星期日算法与程序算法与程序是密切相关的两个概念。研究和讨论算法是为了设计出更好的程序，设计好的算法都要转化为某种语言描述的程序才能在计算机上运行；或者说程序是算法表示的最终形态，程序只有装入计算机中运行（即程序的执行）时才能够起到对实际问题求解的作用。第76页，共92页，编辑于2022年，星期日1.4

46、算法与程序1.4.1程序的基本概念1.4.2问题求解与实现策略1.4.3程序调试与查错策略1.4.4程序设计方法概述第77页，共92页，编辑于2022年，星期日程序的基本概念在低级语言中，程序表现为一组指令和有关数据；在高级语言中，程序表现为一组说明和语句。程序既是软件的固有部分，又是软件研究的对象，程序的质量决定着软件的质量。衡量一个程序的质量，除了对程序结构进行静态考察外，还必须考察其执行过程。与执行无关的特性称之为程序的静态特性，与执行有关的特性称之为程序的动态特性。第78页，共92页，编辑于2022年，星期日程序的特征程序描述解决某一问题的特定任务与功能，回答“解决什么问题”或“做什么

47、”的问题。程序遵循一定的规则和步骤，而不是指令或语句的随意堆砌。程序的执行者是计算机。程序是由人来编写或设计的，是人针对要处理和解决的问题而设计的求解方法和步骤交由计算机操作、运算和处理的说明。程序的运行是自动完成的。程序是算法的程序设计语言描述，但程序并不一定就是算法，因为程序没有有穷性要求。第79页，共92页，编辑于2022年，星期日1.4 算法与程序1.4.1程序的基本概念1.4.2问题求解与实现策略1.4.3程序调试与查错策略1.4.4程序设计方法概述第80页，共92页，编辑于2022年，星期日解决一个实际问题的一般过程明确问题要求。建立数学模型。算法设计。编写程序。调试程序。运行及结

48、果分析。编写程序文档。第81页，共92页，编辑于2022年，星期日程序文档的内容编写文档是最容易被忽视了的一个重要环节。没有文档资料对于软件的维护会带来许多困难，即使是设计者自己也不例外。文档资料要写得完整、清楚和准确，一般应包含如下内容：算法或程序的功能描述和适用范围；运行环境，包括机型、操作系统平台、语言种类、占用空间等；使用说明，即使用该程序的操作命令、I/O格式、各种情况下的操作等说明；流程图及说明；程序清单及注释。第82页，共92页，编辑于2022年，星期日实现策略在拿到一个设计问题之后，有两种不同的方法可供选择：一种是自顶向下逐步求精细化；一种是自底向上逐步堆砌积累。由于人脑思维很

49、难一下子触及问题细节，所以自底向上方法较难运用；即使运用，也难设计出清晰的程序层次结构。结构化程序设计提倡自顶向下逐步求精细化的分析设计方法，从求解问题本身到得出一系列基本操作逐层次展开细化，是一种将问题求解方法由抽象逐步到具体化的过程。采用自顶向下逐步求精细化的设计方法，易于保证和验证程序的正确性。第83页，共92页，编辑于2022年，星期日1.4 算法与程序1.4.1程序的基本概念1.4.2问题求解与实现策略1.4.3程序调试与查错策略1.4.4程序设计方法概述第84页，共92页，编辑于2022年，星期日程序调试程序调试是开发过程中最艰巨的脑力劳动。面对错误征兆，如何在浩如烟海的程序元素中

50、找出有错误的元素，这是调试过程中最关键的技术问题。现有的调试技术有如下三类：输出存储器内容。常以八进制或十六进制形式打印出存储器内容并检查分析。在程序中插入打印语句，调试结束后要将为了调试而插入的语句删掉。借助调试工具。调试工具可以提供程序动态行为的有关信息，但不需要修改源程序。例如，在turbo C中提供了专门的程序调试工具debugger程序。第85页，共92页，编辑于2022年，星期日调试策略试探法回溯法对分查找法归纳法。其步骤为：收集已知的使程序出错与不出错的一切数据；整理数据以发现规律或矛盾；提出关于故障的若干假设；证明假设并据此设法排除故障。演绎法。其步骤为：设想并列出所有可能产生