1、.1前前 言言石志国石志国2引言引言算法设计在计算科学中具有核心的地位和算法设计在计算科学中具有核心的地位和作用，没有好的算法，计算机完成一件工作用，没有好的算法，计算机完成一件工作可能需要作可能需要1年；有好算法，计算机完成一年；有好算法，计算机完成一件工作可能需要几秒。件工作可能需要几秒。算法被公认为是计算科学的基石，翻开重算法被公认为是计算科学的基石，翻开重要的学术刊物，算法都占有一席之地，没要的学术刊物，算法都占有一席之地，没有算法，程序将不复存在。有算法，程序将不复存在。3程序与算法程序与算法要成为编程高手，要有必胜的信心，信心要成为编程高手，要有必胜的信心，信心的来源是建立在扎实的
2、基本功之上的。而的来源是建立在扎实的基本功之上的。而程序员的基本功，无疑就是对程序员的基本功，无疑就是对“算法与数算法与数据结构据结构”的理解。的理解。对算法与数据结构的理解有助于程序员了对算法与数据结构的理解有助于程序员了解语言背后的具体细节，同时，数据结构解语言背后的具体细节，同时，数据结构的定义很大程度上决定了程序的可维护性的定义很大程度上决定了程序的可维护性和可扩展性。因此，算法与数据结构是程和可扩展性。因此，算法与数据结构是程序员信心之源。序员信心之源。4课程简介课程简介本课程涵盖了绝大多数算法设计中的常用技本课程涵盖了绝大多数算法设计中的常用技术。在表达每一种技术时，阐述它的应用背
3、术。在表达每一种技术时，阐述它的应用背景，强调每个算法运转背后的简洁数学思想，景，强调每个算法运转背后的简洁数学思想，注意运用与其他技术类比的方法来说明它的注意运用与其他技术类比的方法来说明它的特征，并提供了大量相应实际问题的例子。特征，并提供了大量相应实际问题的例子。同时也注重了对每一种算法的复杂性分析。同时也注重了对每一种算法的复杂性分析。 5主要内容主要内容全书分成全书分成3部分共部分共10章，从基本的数字算法人手，先后介绍了分治、图的章，从基本的数字算法人手，先后介绍了分治、图的遍历、贪心算法、动态规划等技术。书中每章后面都附有大量的习题，遍历、贪心算法、动态规划等技术。书中每章后面都
4、附有大量的习题，有利于读者对书中内容的理解和应用。有利于读者对书中内容的理解和应用。第一部分第一部分 算法与数据结构基础算法与数据结构基础n第第1章章 算法的基本概念算法的基本概念n第第2章章 C+算法设计基础算法设计基础n第第3章章 线性数据结构基础线性数据结构基础n第第4章章 非线性数据结构基础非线性数据结构基础第二部分第二部分 实用算法与案例解析实用算法与案例解析n第第5章章 实用排序算法基础实用排序算法基础n第第6章章 实用搜索算法基础实用搜索算法基础n第第7章章 递归与分治法递归与分治法n第第8章章 贪心法与动态规划贪心法与动态规划n第第9章章 回溯法与分枝定界回溯法与分枝定界第三部
5、分第三部分 算法综合案例算法综合案例n第第10章章 著名算法与综合案例著名算法与综合案例6算法简介算法简介计算机的问世是计算机的问世是20世纪人类最伟大的发明之一，它把人类世纪人类最伟大的发明之一，它把人类社会带进了信息技术时代，而算法是计算机科学的重要基社会带进了信息技术时代，而算法是计算机科学的重要基础，就像算盘一样，人们需要为计算机编制各种各样的础，就像算盘一样，人们需要为计算机编制各种各样的“口诀口诀”即算法即算法(algorithm)，才能使其工作。，才能使其工作。尽管算法并不给出问题的精确的解，只是说明怎样才能得尽管算法并不给出问题的精确的解，只是说明怎样才能得到解，但是，算法通常
6、都是由有限个操作组成的。这些操到解，但是，算法通常都是由有限个操作组成的。这些操作包括加、减、乘、除、判断、赋值等，并按作包括加、减、乘、除、判断、赋值等，并按顺序、分支、顺序、分支、循环循环等结构组织在一起。等结构组织在一起。7算法的特性：算法的特性：作为一个算法，应该具备如下作为一个算法，应该具备如下5个特性个特性 输入性输入性n一个算法要具有一个算法要具有0个或多个外部量作为算法的输入。这些外部量通常体现为个或多个外部量作为算法的输入。这些外部量通常体现为算法中的一组变量。有些输入量需要在算法执行过程中输入。从表面上看，算法中的一组变量。有些输入量需要在算法执行过程中输入。从表面上看，有
7、些算法好像没有输入量，实际上是输入量已被嵌入到算法之中。有些算法好像没有输入量，实际上是输入量已被嵌入到算法之中。 输出性输出性n一个算法必须具有一个或多个输出，以反映算法对输入数据加工后的结果。一个算法必须具有一个或多个输出，以反映算法对输入数据加工后的结果。没有输出的算法是毫无意义的。没有输出的算法是毫无意义的。 确定性确定性n算法的每一个步骤必须具有确定的定义，即每一步要执行的动作是确定的，算法的每一个步骤必须具有确定的定义，即每一步要执行的动作是确定的，是无二义性的。在任何条件下，算法只有惟一的一条执行路径，即对于相同是无二义性的。在任何条件下，算法只有惟一的一条执行路径，即对于相同的
8、输入得出的输出结果也是相同的。的输入得出的输出结果也是相同的。 有穷性有穷性n对于任何合法的输入值，算法必须在执行有限个步骤之后结束，并且每一步对于任何合法的输入值，算法必须在执行有限个步骤之后结束，并且每一步都可以在有限的时间内完成。都可以在有限的时间内完成。 可行性可行性n算法中描述的操作都是可以通过已经实现的基本运算的有限次执行来实现，算法中描述的操作都是可以通过已经实现的基本运算的有限次执行来实现，即算法的具体实现应该能够被计算机执行。即算法的具体实现应该能够被计算机执行。 8算法的判别依据：算法的判别依据：判断一个算法的好坏主要依据如下判断一个算法的好坏主要依据如下4个标准。个标准。
9、 正确性正确性n正确性是设计一个算法的首要条件，如果一个算法不正确，其它方面正确性是设计一个算法的首要条件，如果一个算法不正确，其它方面就无从谈起。一个正确的算法是指在合理的数据输入下，能在有限的就无从谈起。一个正确的算法是指在合理的数据输入下，能在有限的时间内得出正确的结果。时间内得出正确的结果。 可读性可读性n算法主要是为了人的阅读与交流，其次才是让计算机执行，因此算法算法主要是为了人的阅读与交流，其次才是让计算机执行，因此算法应该易于人的理解；另一方面，晦涩难读的算法易于隐藏较多错误而应该易于人的理解；另一方面，晦涩难读的算法易于隐藏较多错误而使实现该算法的程序的调试工作变得更加困难。使
10、实现该算法的程序的调试工作变得更加困难。 健壮性健壮性n算法应当具备检查错误和对错误进行适当处理的能力。一般而言，处算法应当具备检查错误和对错误进行适当处理的能力。一般而言，处理错误的方法不应是中断程序的执行，而应是返回一个表示错误或错理错误的方法不应是中断程序的执行，而应是返回一个表示错误或错误性质的值，以便在更高的抽象层次上进行处理。误性质的值，以便在更高的抽象层次上进行处理。 效率效率n效率是指算法执行时所需计算机资源的多少，包括运行时间和存储空效率是指算法执行时所需计算机资源的多少，包括运行时间和存储空间两方面的要求。运行时间和存储空间都与问题的规模有关。存储空间两方面的要求。运行时间
11、和存储空间都与问题的规模有关。存储空间指的是算法执行过程中所需的最大存储空间。间指的是算法执行过程中所需的最大存储空间。9算法描述形式算法描述形式 算法的描述形式多种多样，不同的算法描述形式对算法的质算法的描述形式多种多样，不同的算法描述形式对算法的质量有一定的影响。描述同一个算法可以采用自然语言、流程量有一定的影响。描述同一个算法可以采用自然语言、流程图、盒图、伪代码、程序设计语言等。常用的描述算法方法图、盒图、伪代码、程序设计语言等。常用的描述算法方法有如下有如下3种：种： 自然语言描述法自然语言描述法n最简单的描述算法的方法是使用自然语言。用自然语言来描述算法的最简单的描述算法的方法是使
12、用自然语言。用自然语言来描述算法的优点是简单且便于人们对算法的的理解和阅读。缺点是不够严谨，易优点是简单且便于人们对算法的的理解和阅读。缺点是不够严谨，易产生歧义。当算法比较复杂且包含很多转移分支时，用自然语言描述产生歧义。当算法比较复杂且包含很多转移分支时，用自然语言描述就不是那么直观清晰了。就不是那么直观清晰了。 算法框图法算法框图法n使用程序流程图、盒图等算法描述工具来描述算法。其特点是简洁、使用程序流程图、盒图等算法描述工具来描述算法。其特点是简洁、明了，便于理解和交流。明了，便于理解和交流。 伪码语言描述法伪码语言描述法10数据结构数据结构 算法算法 程序程序大部分的算法最终是需要通
13、过能够向计算机发送大部分的算法最终是需要通过能够向计算机发送一系列命令的程序来实现的。所谓一系列命令的程序来实现的。所谓“程序程序”是指是指对所要解决问题的各个对象和处理规则的描述，对所要解决问题的各个对象和处理规则的描述，或者说是数据结构和算法的描述，因此有人说，或者说是数据结构和算法的描述，因此有人说，数据结构数据结构 算法算法 程序。程序。程序与算法不同。程序可以不满足算法的第程序与算法不同。程序可以不满足算法的第个个特性。例如操作系统，它是在无限循环中执行的特性。例如操作系统，它是在无限循环中执行的程序，因而不是算法。然而可把操作系统的各种程序，因而不是算法。然而可把操作系统的各种任务
14、看作一些单独的问题，每一个问题由操作系任务看作一些单独的问题，每一个问题由操作系统中的一个子程序通过特定的算法实现，该子程统中的一个子程序通过特定的算法实现，该子程序得到输出结果后便终止。序得到输出结果后便终止。11算法设计方法算法设计方法算法设计方法主要有：算法设计方法主要有：分治策略、动态规划、贪分治策略、动态规划、贪心算法、回溯法、分支限界、概率算法心算法、回溯法、分支限界、概率算法等，我们等，我们将在后面的章节中陆续介绍。将在后面的章节中陆续介绍。将采用将采用C+语言语言来描述算法。来描述算法。C+语言语言的优点是类的优点是类型丰富、语句精炼，具有面向对象和面向过程的型丰富、语句精炼，
15、具有面向对象和面向过程的双重优点。用双重优点。用C+来描述算法可使整个算法结构来描述算法可使整个算法结构紧凑、可读性强。在课程中，有时为了更好地阐紧凑、可读性强。在课程中，有时为了更好地阐明算法的思路，我们还采用明算法的思路，我们还采用C+与自然语言相结与自然语言相结合的方式来描述算法。合的方式来描述算法。12算法分析的基本原则算法分析的基本原则 正确性正确性 定义：在给定有效输入后，算法经过有限时间的计算并产定义：在给定有效输入后，算法经过有限时间的计算并产生正确的答案，就称算法是正确的。生正确的答案，就称算法是正确的。正确性证明的内容包括：证明算法思路的正确性，证明一正确性证明的内容包括：
16、证明算法思路的正确性，证明一系列与算法的工作对象有关的引理、定理以及公式。系列与算法的工作对象有关的引理、定理以及公式。程序的正确性证明包括：证明所给出的一系列指令确实做程序的正确性证明包括：证明所给出的一系列指令确实做了所要求的工作。了所要求的工作。大型程序的正确性证明，可以将它分解为小的相互独立的大型程序的正确性证明，可以将它分解为小的相互独立的互不相交的模块，分别验证。小模块程序可以使用以下方互不相交的模块，分别验证。小模块程序可以使用以下方法验证：数学归纳法、软件形式方法等。法验证：数学归纳法、软件形式方法等。13占用空间占用空间空间复杂性分析空间复杂性分析 算法在使用计算机表示的时候
17、包括两种占用：算法在使用计算机表示的时候包括两种占用：n1. 存储程序和输入数据的空间；存储程序和输入数据的空间；n2. 存储中间结果或操作单元所占用空间存储中间结果或操作单元所占用空间额外空间。额外空间。影响空间的主要因素包括：影响空间的主要因素包括：n1. 存储程序的空间一般是常数存储程序的空间一般是常数(和输入规模无关和输入规模无关)；n2. 输入数据空间为输入规模输入数据空间为输入规模O(n)；n3. 空间复杂性考虑的是额外空间的大小；空间复杂性考虑的是额外空间的大小；n4. 如果额外空间相对于输入规模是常数，称为原地工如果额外空间相对于输入规模是常数，称为原地工作的算法。作的算法。1
18、4算法分析框架算法分析框架增长次数增长次数 15算法分析框架算法分析框架 渐进符号渐进符号 算法效率的主要指标是基本操作次数的增长次数。算法效率的主要指标是基本操作次数的增长次数。为了对这些增长次数进行比较和归类，计算机科为了对这些增长次数进行比较和归类，计算机科学家们使用了学家们使用了3种符号：种符号：nO（读（读“O”）：上界）：上界n（读（读”omega”）：下界）：下界n（读（读”theta”）：近似）：近似符号符号O定义为：对于足够大的定义为：对于足够大的n，t(n)的上界由的上界由g(n)的常数倍来确定，即：记为的常数倍来确定，即：记为t(n) O(g(n)，t(n) cg(n)，
19、c为常数，例如：为常数，例如：nn O(n2)n100n+5 O(n2)nn(n-1)/2 O(n2)16上界关系如图上界关系如图 17下界关系下界关系符号符号定义为对于足够大的定义为对于足够大的n，t(n)的下界由的下界由g(n)的常数倍来确定，即：记为的常数倍来确定，即：记为t(n) (g(n)，t(n) cg(n)，c为常数。为常数。nn3(n2)nn(n+1)(n2)n4n2+5 (n2)18上界和下界关系上界和下界关系符号符号定义为对于足够大的定义为对于足够大的n，t(n)的上界和下界的上界和下界由由g(n)的常数倍来确定，即：记为的常数倍来确定，即：记为t(n) (g(n)，c2g
20、(n) t(n) c1g(n)，c1, c2为常数。为常数。nn2+3n+2(n2)nn(n-1)/2(n2)n4n2+5 (n2)19渐进符号的用特性渐进符号的用特性定理定理: 如果如果t1(n) O(g1(n)并且并且t2(n)O(g2(n)，则，则t1(n)+ t2(n) O(max(g1(n), g2(n)，对于符号，对于符号和和，该定理也成立。该定理也成立。该定理表明：当算法由两个连续执行部分组成时，该该定理表明：当算法由两个连续执行部分组成时，该算法的整体效率由具有较大增长次数的那部分所决定。算法的整体效率由具有较大增长次数的那部分所决定。20基本的效率类型基本的效率类型 21算法
21、复杂性分析算法复杂性分析 时间复杂度时间复杂度 渐进式的大渐进式的大O形式表示时间复杂度的主要运算规则有如下形式表示时间复杂度的主要运算规则有如下2种：种： 求和规则求和规则nO(f(n)+O(g(n)= O(max(f(n),g(n)n其中，其中，f(n)和和g(n)表示与表示与n有关的一个函数。有关的一个函数。 乘法规则乘法规则nO(f(n)*O(g(n)= O(f(n)*g(n)nO(cf(n)= O(f(n)， c是一个正常数。是一个正常数。假设假设T(n)是问题规模是问题规模n(n为整型数为整型数)的函数，算法的时间复杂的函数，算法的时间复杂度可以定义为度可以定义为O(f(n)，记作
22、：，记作：nT(n) = O(f(n)22对于如下的两个对于如下的两个NN矩阵相乘算法矩阵相乘算法 for ( i = 0; i n; i+)for( j = 0; j n; j+)cij = 0;for( k = 0; k n; k+)cij = cij + aik * bkj;第第1个个for语句的执行次数为语句的执行次数为n+1；第；第2个个for语句的执行次数为语句的执行次数为n(n+1)；语句；语句cij = 0的执行次数是的执行次数是n2；第；第3个个for语句的执语句的执行次数为行次数为n2(n+1)；语句；语句cij = cij + aik * bkj 的执的执行次数是行次数是
23、n3。该算法的时间复杂度为所有语句的执行次数的。该算法的时间复杂度为所有语句的执行次数的总和即：总和即：nT(n)= n+1+ n(n+1)+ n2+ n2(n+1)+ n3=2n3+3n2+2n+1如果根据渐进式大如果根据渐进式大O规则，则该算法的时间复杂度为规则，则该算法的时间复杂度为O(n3)。23时间复杂度分析的一些基本规则时间复杂度分析的一些基本规则 对于简单的输入、输出及赋值语句，执行时间为对于简单的输入、输出及赋值语句，执行时间为O(1)。 对于顺序结构，需要执行一系列语句所用时间可采用渐进式大对于顺序结构，需要执行一系列语句所用时间可采用渐进式大O的的求和规则来进行计算。求和规
24、则来进行计算。 对于选择结构，它的时间复杂度主要体现在对条件判断后所执行的对于选择结构，它的时间复杂度主要体现在对条件判断后所执行的语句上。如下列判断语句：语句上。如下列判断语句：if(c)s1;elses2;判断语句所需要的执行时间为：判断语句所需要的执行时间为：O(1)执行语句所需要的执行时间为：执行语句所需要的执行时间为：O(max(T(s1),T(s2) 对于循环结构，它的时间复杂度主要体现在循环体语句及循环条件对于循环结构，它的时间复杂度主要体现在循环体语句及循环条件判断语句上，可以利用渐进式大判断语句上，可以利用渐进式大O的乘积规则来进行计算。的乘积规则来进行计算。 对于复杂的算法，可以将它分割成几个容易估算的部分，然后利用对于复杂的算法，可以将它分割成几个容易估算的部分，然后利用渐进式大渐进式大O的求和规则与乘法规则计算整个算法的时间复杂度。的求和规则与乘法规则计算整个算法的时间复杂度。24小结小结本章介绍了算法的基本概念，简要的说明本章介绍了算法的基本概念，简要的说明了算法描述的形式以及分析的基本原则，了算法描述的形式以及分析的基本原则，从整体上分析了算法的框架从整体上分析了算法的框架并介绍了并介绍了3种常用的渐进符号。同时简要介种常用的渐进符号。同时简要介绍了时间复杂度和空间复杂度。绍了时间复杂度和空间复杂度。个人观点供参考，欢迎讨论！
