第1章绪论

1.1什么是算法

1.1.1算法的由来

1.1.2算法的发展

1.1.3算法的例子

1.2重要的问题类型

1.2.1排序

1.2.2查找

1.2.3字符串匹配

1.2.4图问题

1.2.5组合问题

1.2.6几何问题

1.2.7数值问题

1.3基本数据结构

1.3.1线性结构

1.3.2树结构

1.3.3图结构

1.3.4集合

1.3.5数据的物理结构

1.4算法问题求解基础

1.4.1算法求解框架

1.4.2算法设计步骤

1.5算法的表示

1.6为什么学习算法

总结

习题1

第2章算法效率分析基础

2.1算法分析框架

2.1.1算法分析概述

2.1.2算法正确性分析

2.1.3时空效率分析

2.1.4算法分析过程

2.2渐进符号和基本效率类型

2.2.1三种渐进符号

2.2.2渐进符号的特性

2.2.3基本效率类型

2.3非递归算法的数学分析方法

2.4递归算法的数学分析

2.4.1递归算法的数学分析方法

2.4.2斐波那契数列

2.5算法的其他分析方法

总结

习题2

第3章蛮力法

3.1概述

3.2排序问题

3.2.1选择排序

3.2.2冒泡排序

3.3查找问题

3.3.1顺序查找

3.3.2字符串匹配

3.4几何问题

3.4.1最近对问题

3.4.2凸包问题

3.5组合问题

3.5.1旅行商问题

3.5.2背包问题

总结

习题3

第4章分治法

4.1概述

4.2分治法的基本策略及步骤

4.2.1分治法的基本策略

4.2.2分治法的基本步骤

4.3排序问题

4.3.1合并排序

4.3.2快速排序

4.4查找问题

4.4.1折半查找

4.4.2二叉树遍历及其相关特性

4.5数值计算问题

4.5.1大整数乘法

4.5.2Strassen矩阵乘法

4.6几何问题

4.6.1用分治法解最近对问题

4.6.2用分治法解凸包问题

4.7分析分治法在安排循环赛中的应用

总结

习题4

第5章分治策略变体——减治策略和变治策略

5.1减治策略

5.1.1插入排序

5.1.2拓扑排序

5.1.3生成组合对象的算法

5.1.4减常因子算法

5.1.5减可变规模算法

5.2变治策略

5.2.1排序问题

5.2.2平衡查找树

5.2.3霍纳法则和二进制幂

5.2.4问题化简

总结

习题5

第6章动态规划

6.1概述

6.2算法特点

6.2.1备忘录方法

6.2.2最优化原理

6.2.3求解步骤

6.3矩阵连乘问题

6.4最长公共子序列

6.501背包问题

6.6最大子段和

6.7最优二叉查找树

总结

习题6

第7章时空权衡技术

7.1时空权衡策略

7.2计数排序

7.3字符串匹配

7.4散列法

总结

习题7

第8章贪心算法

8.1概述

8.1.1贪心算法的基本要素

8.1.2贪心算法的求解过程

8.2活动安排问题

8.3背包问题

8.4最小生成树问题

8.4.1Prim算法

8.4.2Kruskal算法

8.5单源(点)最短路径问题

8.6哈夫曼编码

总结

习题8

第9章回溯法和分支限界法

9.1回溯法

9.1.1概述

9.1.2子集和问题

9.1.3n皇后问题

9.1.4哈密顿回路

9.1.5装载问题

9.2分支限界法

9.2.1概述

9.2.201背包问题

9.2.3任务分配问题

9.2.4多段图的最短路径问题

9.2.5旅行商问题

总结

习题9

第10章NP完全性理论

10.1判定问题和最优化问题

10.2P类问题

10.3NP类问题

10.4NP完全问题

10.5典型的NP完全问题

10.6其他NP完全问题

10.7NP完全问题的计算机处理

总结

习题10

第11章案例精选

11.1果园篱笆问题

11.2空中飞行管理问题

11.3去数问题

11.4极差问题

11.5最优合并问题

11.6在棋盘中实现从初始布局到目标布局的转变

11.7商店购物问题

11.8旅游预算问题

11.9防卫导弹问题

11.10钓鱼问题

11.11胖男孩问题

11.12护卫队问题

参考文献