文档介绍：数据结构与算法算法设计与分析
*
主要内容介绍
第1章 算法引论
第2章 递归与分治策略
第3章 动态规划
第4章 贪心算法
第5章 回溯法
第6章 分支限界法
数据结构与算法算法设计与分析
*
主要内容介绍（续）
第7章 概率算法
第8章 NP完全性理论
第9章 近似算法
第10章 算法优化策略
数据结构与算法算法设计与分析
*
第1章 算法引论
算法与程序
表达算法的抽象机制
描述算法
算法复杂性分析
本章主要知识点：
数据结构与算法算法设计与分析
*
算法与程序
输 入：有零个或多个外部量作为算法的输入。
输 出：算法产生至少一个量作为输出。
确定性：组成算法的每条指令清晰、无歧义。
有限性：算法中每条指令的执行次数有限，执行每条指令的时间也有限。
是算法用某种程序设计语言的具体实现。
程序可以不满足算法的性质(4)即有限性。
是满足下述性质的指令序列。
算法：
程序：
数据结构与算法算法设计与分析
*
表达算法的抽象机制
高级程序设计语言的主要好处是：
（4）把繁杂琐碎的事务交给编译程序，所以自动化程度高，开发周期短，程序员可以集中时间和精力从事更重要的创造性劳动，提高程序质量。
（1）高级语言更接近算法语言，易学、易掌握，一般工程技术人员只需 要几周时间的培训就可以胜任程序员的工作；
（2）高级语言为程序员提供了结构化程序设计的环境和工具，使得设计出来的程序可读性好，可维护性强，可靠性高；
（3）高级语言不依赖于机器语言，与具体的计算机硬件关系不大，因而所写出来的程序可植性好、重用率高；
数据结构与算法算法设计与分析
*
表达算法的抽象机制
抽象数据类型是算法的一个数据模型连同定义在该模型上
并作为算法构件的一组运算。
抽象数据类型带给算法设计的好处有：
（1）算法顶层设计与底层实现分离；
（2）算法设计与数据结构设计隔开，允许数据结构自由选择；
（3）数据模型和该模型上的运算统一在ADT中，便于空间和时间耗费的折衷；
（4）用抽象数据类型表述的算法具有很好的可维护性；
（5）算法自然呈现模块化；
（6）为自顶向下逐步求精和模块化提供有效途径和工具；
（7）算法结构清晰，层次分明，便于算法正确性的证明和复杂性的分析。
数据结构与算法算法设计与分析
*
在本书中，采用Java语言描述算法。
描述算法
以下，对Java语言的若干重要特性作简要概述。
（1）Java程序的两种类型：应用程序和applet
区别：应用程序的主方法为main，其可在命令行中用命令
语句 java 应用程序名 来执行；
applet的主方法为init，其必须嵌入HTML文件，由
Web浏览器或applet阅读器来执行。
（2）包：java程序和类可以包(packages)的形式组织管理。
（3）import语句：在java程序中可用import语句加载所需的包。
例如，import .*;语句加载包。
数据结构与算法算法设计与分析
*
描述算法
数据类型
基本数据类型：详见下页表1-1
非基本数据类型：如 Byte, Integer, Boolean, String等。
Java对两种数据类型的不同处理方式：
对基本数据类型：在声明一个具有基本数据类型的变量时，自
动建立该数据类型的对象（或称实例）。如:int k;
对非基本数据类型：语句 String s; 并不建立具有数据类型
String的对象，而是建立一个类型String的引用对象，
数据类型为String的对象可用下面的new语句建立。
s = new String(“Welcome”);
String s = new String(“Welcome”);
数据结构与算法算法设计与分析
*
描述算法
表格1-1 Java基本数据类型
类型
缺省值
分配空间（bits）
取值范围
boolean
false
1
[true,false]
byte
0
8
[-128,127]
char
\u0000
16
[\u0000,\uFFFF]
double
64
±*10-324 ~ ±*10308
float
32
±*10-45 ~ ±*1038
int
0
32
[-2147483648,2147483647]
long
0
64
±9