文档介绍：第1章 算法分析基本概念
朱友文
******@
《算法设计技巧与分析》
课程主页
南京航空航天大学 计算机学院
2015/3/11
2
课程内容 (40学时)
第1-10周，周一5-6节，周三1-2节
常用的算法设计策略(包括分治策略、动态规划、贪心策略、回溯法、随机算法等)
算法复杂度分析方法(计算迭代次数、使用递归方程、频度分析等)
2015/3/11
3
南京航空航天大学 计算机学院
课程要求
掌握常用的算法设计策略、算法复杂度分析方法
授课方式：讲授
考核方式：闭卷笔试
2015/3/11
4
南京航空航天大学 计算机学院
教材
《算法设计技巧与分析》，M. H. Alsuwaiyel著, 电子工业出版社，吴伟昶等译，2010
2015/3/11
5
南京航空航天大学 计算机学院
相关参考文献
Algorithm Design Techniques and Analysis, M. H. Alsuwaiyel. (影印本). 电子工业出版社.
算法导论(第2版)，Thomas H. Cormen等著，潘金贵等译，机械工业出版社.
计算机算法设计与分析(第3版), 王晓东, 电子工业出版社,.
算法设计与分析，王红梅编著， 清华大学出版社.
2015/3/11
6
南京航空航天大学 计算机学院
2015/3/11
南京航空航天大学 计算机学院
7
1. 1 引言
Donald E. Knuth: 计算机科学就是算法的研究.
每个领域: 依赖 有效算法设计
运行时间:
时间是衡量算法有效性的最好测度
算法的几个方面：
输入
有限指令集
输出 (存在? Y/N)
2015/3/11
南京航空航天大学 计算机学院
8
算法和程序关系
算法是程序设计的核心，程序设计本质上是用特定的语言实现并细化构造解决问题的算法，将其解释为计算机语言。
算法是在有限步骤内求解某一问题所使用的一组定义明确的指令（规则）。通俗点说，就是计算机解题的过程。在这个过程中，无论是形成解题思路还是编写程序，都是在实施某种算法。前者是推理实现的算法，后者是操作实现的算法。
2015/3/11
南京航空航天大学 计算机学院
9
程序是算法用某种程序设计语言的具体实现。
程序可以不满足算法的有限性的性质。
例如操作系统，是一个在无限循环中执行的程序，因而不是一个算法。
操作系统的各种任务可看成是单独的问题，每一个问题由操作系统中的一个子程序通过特定的算法来实现。该子程序得到输出结果后便终止。
程序(Program)
算法具有五个重要的特征
有穷性： 算法必须执行有限步之后结束；
确切性： 算法的每一步必须有确切的定义；
输入：算法有0个或多个输入，以刻画运算对象的初始情况；
输出：算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的；
可行性： 算法原则上能够精确地运行，而且人们用笔和纸做有限次运算后即可完成。
2015/3/11
南京航空航天大学 计算机学院
10