《程序与算法》ppt课件

《《程序与算法》ppt课件》由会员分享，可在线阅读，更多相关《《程序与算法》ppt课件（24页珍藏版）》请在金锄头文库上搜索。

1、前 言,石志国,算法设计在计算科学中具有核心的地位和作用，没有好的算法，计算机完成一件工作可能需要1年；有好算法，计算机完成一件工作可能需要几秒。 算法被公认为是计算科学的基石，翻开重要的学术刊物，算法都占有一席之地，没有算法，程序将不复存在。,程序与算法,要成为编程高手，要有必胜的信心，信心的来源是建立在扎实的基本功之上的。而程序员的基本功，无疑就是对“算法与数据结构”的理解。 对算法与数据结构的理解有助于程序员了解语言背后的具体细节，同时，数据结构的定义很大程度上决定了程序的可维护性和可扩展性。因此，算法与数据结构是程序员信心之源。,课程简介,本课程涵盖了绝大多数算法设计中的常用技术。在表

2、达每一种技术时，阐述它的应用背景，强调每个算法运转背后的简洁数学思想，注意运用与其他技术类比的方法来说明它的特征，并提供了大量相应实际问题的例子。 同时也注重了对每一种算法的复杂性分析。,主要内容,全书分成3部分共10章，从基本的数字算法人手，先后介绍了分治、图的遍历、贪心算法、动态规划等技术。书中每章后面都附有大量的习题，有利于读者对书中内容的理解和应用。 第一部分 算法与数据结构基础 第1章 算法的基本概念 第2章 C+算法设计基础 第3章 线性数据结构基础 第4章 非线性数据结构基础 第二部分 实用算法与案例解析 第5章 实用排序算法基础 第6章 实用搜索算法基础 第7章 递归与分治法

3、第8章 贪心法与动态规划 第9章 回溯法与分枝定界 第三部分 算法综合案例 第10章 著名算法与综合案例,算法简介,计算机的问世是20世纪人类最伟大的发明之一，它把人类社会带进了信息技术时代，而算法是计算机科学的重要基础，就像算盘一样，人们需要为计算机编制各种各样的“口诀”即算法(algorithm)，才能使其工作。 尽管算法并不给出问题的精确的解，只是说明怎样才能得到解，但是，算法通常都是由有限个操作组成的。这些操作包括加、减、乘、除、判断、赋值等，并按顺序、分支、循环等结构组织在一起。,算法的特性：,作为一个算法，应该具备如下5个特性 输入性 一个算法要具有0个或多个外部量作为算法的输入。

4、这些外部量通常体现为算法中的一组变量。有些输入量需要在算法执行过程中输入。从表面上看，有些算法好像没有输入量，实际上是输入量已被嵌入到算法之中。 输出性 一个算法必须具有一个或多个输出，以反映算法对输入数据加工后的结果。没有输出的算法是毫无意义的。 确定性 算法的每一个步骤必须具有确定的定义，即每一步要执行的动作是确定的，是无二义性的。在任何条件下，算法只有惟一的一条执行路径，即对于相同的输入得出的输出结果也是相同的。 有穷性 对于任何合法的输入值，算法必须在执行有限个步骤之后结束，并且每一步都可以在有限的时间内完成。 可行性 算法中描述的操作都是可以通过已经实现的基本运算的有限次执行来实现，

5、即算法的具体实现应该能够被计算机执行。,算法的判别依据：,判断一个算法的好坏主要依据如下4个标准。 正确性 正确性是设计一个算法的首要条件，如果一个算法不正确，其它方面就无从谈起。一个正确的算法是指在合理的数据输入下，能在有限的时间内得出正确的结果。 可读性 算法主要是为了人的阅读与交流，其次才是让计算机执行，因此算法应该易于人的理解；另一方面，晦涩难读的算法易于隐藏较多错误而使实现该算法的程序的调试工作变得更加困难。 健壮性 算法应当具备检查错误和对错误进行适当处理的能力。一般而言，处理错误的方法不应是中断程序的执行，而应是返回一个表示错误或错误性质的值，以便在更高的抽象层次上进行处理。 效

6、率 效率是指算法执行时所需计算机资源的多少，包括运行时间和存储空间两方面的要求。运行时间和存储空间都与问题的规模有关。存储空间指的是算法执行过程中所需的最大存储空间。,算法描述形式,算法的描述形式多种多样，不同的算法描述形式对算法的质量有一定的影响。描述同一个算法可以采用自然语言、流程图、盒图、伪代码、程序设计语言等。常用的描述算法方法有如下3种： 自然语言描述法 最简单的描述算法的方法是使用自然语言。用自然语言来描述算法的优点是简单且便于人们对算法的的理解和阅读。缺点是不够严谨，易产生歧义。当算法比较复杂且包含很多转移分支时，用自然语言描述就不是那么直观清晰了。 算法框图法 使用程序流程图、

7、盒图等算法描述工具来描述算法。其特点是简洁、明了，便于理解和交流。 伪码语言描述法,数据结构 算法 程序,大部分的算法最终是需要通过能够向计算机发送一系列命令的程序来实现的。所谓“程序”是指对所要解决问题的各个对象和处理规则的描述，或者说是数据结构和算法的描述，因此有人说，数据结构 算法 程序。 程序与算法不同。程序可以不满足算法的第个特性。例如操作系统，它是在无限循环中执行的程序，因而不是算法。然而可把操作系统的各种任务看作一些单独的问题，每一个问题由操作系统中的一个子程序通过特定的算法实现，该子程序得到输出结果后便终止。,算法设计方法,算法设计方法主要有：分治策略、动态规划、贪心算法、回溯

8、法、分支限界、概率算法等，我们将在后面的章节中陆续介绍。 将采用C+语言来描述算法。C+语言的优点是类型丰富、语句精炼，具有面向对象和面向过程的双重优点。用C+来描述算法可使整个算法结构紧凑、可读性强。在课程中，有时为了更好地阐明算法的思路，我们还采用C+与自然语言相结合的方式来描述算法。,算法分析的基本原则 正确性,定义：在给定有效输入后，算法经过有限时间的计算并产生正确的答案，就称算法是正确的。 正确性证明的内容包括：证明算法思路的正确性，证明一系列与算法的工作对象有关的引理、定理以及公式。 程序的正确性证明包括：证明所给出的一系列指令确实做了所要求的工作。 大型程序的正确性证明，可以将它

9、分解为小的相互独立的互不相交的模块，分别验证。小模块程序可以使用以下方法验证：数学归纳法、软件形式方法等。,占用空间空间复杂性分析,算法在使用计算机表示的时候包括两种占用： 1. 存储程序和输入数据的空间； 2. 存储中间结果或操作单元所占用空间额外空间。 影响空间的主要因素包括： 1. 存储程序的空间一般是常数(和输入规模无关)； 2. 输入数据空间为输入规模O(n)； 3. 空间复杂性考虑的是额外空间的大小； 4. 如果额外空间相对于输入规模是常数，称为原地工作的算法。,算法分析框架增长次数,算法分析框架 渐进符号,算法效率的主要指标是基本操作次数的增长次数。为了对这些增长次数进行比较和归

10、类，计算机科学家们使用了3种符号： O（读“O”）：上界 （读”omega”）：下界 （读”theta”）：近似 符号O定义为：对于足够大的n，t(n)的上界由g(n)的常数倍来确定，即：记为t(n) O(g(n)，t(n) cg(n)，c为常数，例如： n O(n2) 100n+5 O(n2) n(n-1)/2 O(n2),上界关系如图,下界关系,符号定义为对于足够大的n，t(n)的下界由g(n)的常数倍来确定，即：记为t(n) (g(n)，t(n) cg(n)，c为常数。 n3(n2) n(n+1)(n2) 4n2+5 (n2),上界和下界关系,符号定义为对于足够大的n，t(n)的上界和下

11、界由g(n)的常数倍来确定，即：记为t(n) (g(n)，c2g(n) t(n) c1g(n)，c1, c2为常数。 n2+3n+2(n2) n(n-1)/2(n2) 4n2+5 (n2),渐进符号的用特性,定理: 如果t1(n) O(g1(n)并且t2(n)O(g2(n)，则t1(n)+ t2(n) O(max(g1(n), g2(n)，对于符号和，该定理也成立。 该定理表明：当算法由两个连续执行部分组成时，该算法的整体效率由具有较大增长次数的那部分所决定。,基本的效率类型,算法复杂性分析 时间复杂度,渐进式的大O形式表示时间复杂度的主要运算规则有如下2种： 求和规则 O(f(n)+O(g(

12、n)= O(max(f(n),g(n) 其中，f(n)和g(n)表示与n有关的一个函数。 乘法规则 O(f(n)*O(g(n)= O(f(n)*g(n) O(cf(n)= O(f(n)， c是一个正常数。 假设T(n)是问题规模n(n为整型数)的函数，算法的时间复杂度可以定义为O(f(n)，记作： T(n) = O(f(n),对于如下的两个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

13、语句的执行次数为n(n+1)；语句cij = 0的执行次数是n2；第3个for语句的执行次数为n2(n+1)；语句cij = cij + aik * bkj 的执行次数是n3。该算法的时间复杂度为所有语句的执行次数的总和即： T(n)= n+1+ n(n+1)+ n2+ n2(n+1)+ n3=2n3+3n2+2n+1 如果根据渐进式大O规则，则该算法的时间复杂度为O(n3)。,时间复杂度分析的一些基本规则, 对于简单的输入、输出及赋值语句，执行时间为O(1)。 对于顺序结构，需要执行一系列语句所用时间可采用渐进式大O的求和规则来进行计算。 对于选择结构，它的时间复杂度主要体现在对条件判断后所执行的语句上。如下列判断语句： if(c)s1;elses2; 判断语句所需要的执行时间为：O(1) 执行语句所需要的执行时间为：O(max(T(s1),T(s2) 对于循环结构，它的时间复杂度主要体现在循环体语句及循环条件判断语句上，可以利用渐进式大O的乘积规则来进行计算。 对于复杂的算法，可以将它分割成几个容易估算的部分，然后利用渐进式大O的求和规则与乘法规则计算整个算法的时间复杂度。,小结,本章介绍了算法的基本概念，简要的说明了算法描述的形式以及分析的基本原则，从整体上分析了算法的框架 并介绍了3种常用的渐进符号。同时简要介绍了时间复杂度和空间复杂度。,