第1章+算法概述ppt课件.ppt

《第1章+算法概述ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第一章算法概述理解算法的概念。理解什么是程序，程序与算法的区别和内在联系。掌握算法的计算复杂性概念。掌握算法渐近复杂性的数学表述。学习要点:2提纲一、算法与程序二、算法复杂性分析3提纲一、算法与程序二、算法复杂性分析4什么是算法(Algorithms)？算法是指解决问题的方法和过程。算法是对特定问题求解步骤的一种描述，包含操作的有限规则和操作的有限序列。通俗一点讲，算法就是一个解决问题的公式（数学手册上的公式都是经典算法）、规则、思路、方法和步骤。算法可以用自然语言描述，也可以用流程图描述，但最终要用计算机语言编程，上机实现。5算法的特性算法是若干指令的

2、有穷序列，满足性质：确定性：每条指令的意义都是清晰的，无歧义的；有限性：每条指令的执行次数和执行时间都是有限的；如：不允许有诸如“x/0”或“x与1或2相加”之类的运算。因为前者结果不能确定，而后者不能确定两种可能的运算应该执行哪一个。输入：有零个或多个输入；输出：至少产生一个量作为输出。如：如果算法中的循环步长为零，运算进入无限循环，这是不允许的。算法要求其执行时间是有限的(终止性)。6程序(Program)程序是算法用某种程序设计语言的具体实现。程序是依赖于程序设计语言的，甚至依赖于计算机结构的。算法是脱离具体的计算机结构和程序设计语言的。7算法与程

3、序的区别与联系一个程序不一定满足有限性。例操作系统，只要整个系统不遭破坏，它将永远不会停止，即使没有作业需要处理，它仍处于动态等待中。因此，操作系统不是一个算法。程序中的指令必须是机器可执行的，而算法中的指令则无此限制。算法代表了对问题的解，而程序则是算法在计算机上的特定的实现。一个算法若用程序设计语言来描述，则它就是一个程序.8问题求解(ProblemSolving)证明正确性分析算法设计程序理解问题精确解或近似解选择数据结构算法设计策略设计算法9算法≠程序算法描述：自然语言，流程图，程序设计语言，伪代码用各种算法描述方法所描述的同一算法，该算法的功用

4、是一样的，允许在算法的描述和实现方法上有所不同。本书中采用类C++伪代码语言描述算法。算法描述人们的生产活动和日常生活离不开算法，都在自觉不自觉地使用算法，例如人们到商店购买物品，会首先确定购买哪些物品，准备好所需的钱，然后确定到哪些商场选购、怎样去商场、行走的路线，若物品的质量好如何处理，对物品不满意又怎样处理，购买物品后做什么等。以上购物的算法是用自然语言描述的，也可以用其他描述方法描述该算法。10问题表示设Input和Output是两个集合。一个问题是一个关系RInputOutput，Input称为问题R的输入集合，Input的每个元素称为R的

5、一个输入，Output称为问题R的输出或结果集合，Output的每个元素称为R的一个结果。一个算法面向一类问题，而不是仅求解问题的一个或几个实例。11排序问题例如，排序（SORT）问题定义如下：－Input=ai是实数－output=bi是实数,且b1...bn－R=(,)Input，output,a1,...,an=b1,...,bn}12算法示例—插入排序算法a0,...,n-1=

6、5,2,4,6,1,3a0,...,n-1=5,2,4,6,1,3a0,...,n-1=2,5,4,6,1,3a0,...,n-1=2,4,5,6,1,3a0,...,n-1=2,4,5,6,1,3a0,...,n-1=1,2,4,5,6,3a0,...,n-1=1,2,3,4,5,6算法的思想：扑克牌游戏13算法描述从第一个元素开始，该元素可以认为已经被排序取出下一个元素，在已经排序的元素序列中从后向前扫描如果该元素（已排序）大于新元素，将该元素移到下一位置重复步骤3，直到找到已排序的元素小于或者等于新元素的位置将新元素插入到该

7、位置中重复步骤214templatevoidInsertionSort(Type*a,intn)//数组a中包含了n个待排序的数.{Typekey;for(inti=1;i=0&&a[j]>key){a[j+1]=a[j];j--;}a[j+1]=key;}}插入排序算法15算法的正确性分析正确的算法：对于每一个输入都最终停止,而且产生正确的输出。不正确算法：①不停止(在某个输入上

8、)②对所有输入都停止，但对某输入产生不正确结果近似算法①对所有输入都停止②产生近