文档介绍：中国计算机学会 21世纪大学本科计算机专业系列教材 《算法设计与分析》
王晓东 编著
巢湖学院计算机科学与技术系
主要内容介绍
第1章、算法引论
第2章、递归与分治策略
第3章、动态规划
第4章、贪心算法
第5章、回溯法
第6章、分支限界法
第7章、概率算法
第8章、NP完全性理论
第9章、近似算法
第10章、算法优化策略
巢湖学院计算机科学与技术系
第1章算法引论
算法与程序
表达算法的抽象机制
描述算法
算法复杂性分析
本章主要知识点:
巢湖学院计算机科学与技术系
、算法与程序
算法:是指解决问题的一种方法或一个过程,在计算机领域是指满足下述性质的指令序列。
(1)输入:有外部提供的量作为算法的输入。
(2)输出:算法产生至少一个量作为输出。
(3)确定性:组成算法的每条指令是清晰,无歧义的。
(4)有限性:算法中每条指令的执行次数是有限的,执行每条指令的时间也是有限的。
巢湖学院计算机科学与技术系
、算法与程序
程序:是算法用某种程序设计语言的具体实现。
程序可以不满足算法的性质(4)。
例如操作系统,是一个在无限循环中执行的程序,因而不是一个算法。
操作系统的各种任务可看成是单独的问题,每一个问题由操作系统中的一个子程序通过特定的算法来实现。该子程序得到输出结果后便终止。
巢湖学院计算机科学与技术系
问题求解(Problem Solving)
证明正确性
分析算法
设计程序
理解问题
精确解或近似解
选择数据结构
算法设计策略
设计算法
巢湖学院计算机科学与技术系
、表达算法的抽象机制
高级程序设计语言的主要好处是:
(4)把繁杂琐碎的事务交给编译程序,所以自动化程度高,开发周期短,程序员可以集中时间和精力从事更重要的创造性劳动,提高程序质量。
(1)高级语言更接近算法语言,易学、易掌握,一般工程技术人员只需要几周时间的培训就可以胜任程序员的工作;
(2)高级语言为程序员提供了结构化程序设计的环境和工具,使得设计出来的程序可读性好,可维护性强,可靠性高;
(3)高级语言不依赖于机器语言,与具体的计算机硬件关系不大,因而所写出来的程序可植性好、重用率高;
巢湖学院计算机科学与技术系
、表达算法的抽象机制
抽象数据类型是算法的一个数据模型连同定义在该模型上,并作为算法构件的一组运算。
抽象数据类型带给算法设计的好处有:
(1)算法顶层设计与底层实现分离;
(2)算法设计与数据结构设计隔开,允许数据结构自由选择;
(3)数据模型和该模型上的运算统一在ADT中,便于空间和时间耗费的折衷;
(4)用抽象数据类型表述的算法具有很好的可维护性;
(5)算法自然呈现模块化;
(6)为自顶向下逐步求精和模块化提供有效途径和工具;
(7)算法结构清晰,层次分明,便于算法正确性的证明和复杂性的分析。
巢湖学院计算机科学与技术系
、算法复杂性分析
算法复杂性是算法运行所需要的计算机资源的量,需要时间资源的量称为时间复杂性T(N) ,需要的空间资源的量称为空间复杂性S(N) 。这个量应该只依赖于算法要解的问题的规模、算法的输入和算法本身的函数。如果分别用N、I和A表示算法要解问题的规模、算法的输入和算法本身,而且用C表示复杂性,那么,应该有C=F(N,I,A)。
一般把时间复杂性和空间复杂性分开,分别用T和S来表示
则有: T=T(N,I)和S=S(N,I) 。
(通常,让A隐含在复杂性函数名当中)
巢湖学院计算机科学与技术系
、算法复杂性分析
最坏情况下的时间复杂性:
最好情况下的时间复杂性:
平均情况下的时间复杂性:
其中DN 是规模为N的合法输入的集合;I*是DN中使T(N, I*)
达到Tmax(N)的合法输入; 是中使T(N, )达到Tmin(N)的合法
输入;而P(I)是在算法的应用中出现输入I的概率。
巢湖学院计算机科学与技术系