目 录__eol____eol__第一部分 基本概念和算法导引第1章 算法分析基本概念__eol____eol__ 1.1 引言__eol____eol__ 1.2 历史背景__eol____eol__ 1.3 二分搜索__eol____eol__ 1.4 合并两个已排序的表__eol____eol__ 1.5 选择排序__eol____eol__ 1.6 插入排序__eol____eol__ 1.7 自底向上合并排序__eol____eol__ 1.8 时间复杂性__eol____eol__ 1.9 空间复杂性__eol____eol__ 1.10 最优算法__eol____eol__ 1.11 如何估计算法的运行时间__eol____eol__ 1.12 最坏情况和平均情况的分析__eol____eol__ 1.13 平摊分析__eol____eol__ 1.14 输入大小和问题实例__eol____eol__ 1.15 分治递推式__eol____eol__ 1.16 练习__eol____eol__ 1.17 参考注释第2章 数据结构__eol____eol__ 2.1 引言__eol____eol__ 2.2 链表__eol____eol__ 2.3 图__eol____eol__ 2.4 树__eol____eol__ 2.5 根树__eol____eol__ 2.6 二叉树__eol____eol__ 2.7 练习__eol____eol__ 2.8 参考注释第3章 堆和不相交集数据结构__eol____eol__ 3.1 引言__eol____eol__ 3.2 堆__eol____eol__ 3.3 不相交集数据结构__eol____eol__ 3.4 练习__eol____eol__ 3.5 参考注释__eol____eol__第二部分 基于递归的技术第4章 归纳法__eol____eol__ 4.1 引言__eol____eol__ 4.2 寻找多数元素__eol____eol__ 4.3 整数幂__eol____eol__ 4.4 多项式求值（Horner规则）__eol____eol__ 4.5 基数排序__eol____eol__ 4.6 生成排列__eol____eol__ 4.7 练习__eol____eol__ 4.8 参考注释第5章 分治__eol____eol__ 5.1 引言__eol____eol__ 5.2 二分搜索__eol____eol__ 5.3 合并排序__eol____eol__ 5.4 分治范式__eol____eol__ 5.5 选择： 寻找中项和第k小的元素__eol____eol__ 5.6 快速排序__eol____eol__ 5.7 多选__eol____eol__ 5.8 大整数乘法__eol____eol__ 5.9 矩阵乘法__eol____eol__ 5.10 最近点对问题__eol____eol__ 5.11 练习__eol____eol__ 5.12 参考注释第6章 动态规划__eol____eol__ 6.1 引言__eol____eol__ 6.2 最长公共子序列问题__eol____eol__ 6.3 矩阵链相乘__eol____eol__ 6.4 动态规划范式__eol____eol__ 6.5 所有点对的最短路径问题__eol____eol__ 6.6 背包问题__eol____eol__ 6.7 练习__eol____eol__ 6.8 参考注释__eol____eol__第三部分 最先割技术第7章 贪心算法__eol____eol__ 7.1 引言__eol____eol__ 7.2 最短路径问题__eol____eol__ 7.3 最小耗费生成树（Kruskal算法）__eol____eol__ 7.4 最小耗费生成树(Prim算法)__eol____eol__ 7.5 文件压缩__eol____eol__ 7.6 练习__eol____eol__ 7.7 参考注释第8章 图的遍历__eol____eol__ 8.1 引言__eol____eol__ 8.2 深度优先搜索__eol____eol__ 8.3 深度优先搜索的应用__eol____eol__ 8.4 广度优先搜索__eol____eol__ 8.5 广度优先搜索的应用__eol____eol__ 8.6 练习__eol____eol__ 8.7 参考注释__eol____eol__第四部分 问题的复杂性第9章 NP完全问题__eol____eol__ 9.1 引言__eol____eol__ 9.2 P类__eol____eol__ 9.3 NP类__eol____eol__ 9.4 NP完全问题的分析__eol____eol__ 9.5 coNP类__eol____eol__ 9.6 三种复杂性类之间的关系__eol____eol__ 9.7 练习__eol____eol__ 9.8 参考注释第10章 计算复杂性引论__eol____eol__ 10.1 引言__eol____eol__ 10.2 计算模型：图灵机__eol____eol__ 10.3 k带图灵机和时间复杂性__eol____eol__ 10.4 离线图灵机和空间复杂性__eol____eol__ 10.5 带压缩和线性加速__eol____eol__ 10.6 复杂性类之间的关系__eol____eol__ 10.7 归约__eol____eol__ 10.8 完全性__eol____eol__ 10.9 多项式时间层次__eol____eol__ 10.10 练习__eol____eol__ 10.11 参考注释第11章 下界__eol____eol__ 11.1 引言__eol____eol__ 11.2 平凡下界__eol____eol__ 11.3 决策树模型__eol____eol__ 11.4 代数决策树模型__eol____eol__ 11.5 线性时间归约__eol____eol__ 11.6 练习__eol____eol__ 11.7 参考注释__eol____eol__第五部分 克服困难性第12章 回溯法__eol____eol__ 12.1 引言__eol____eol__ 12.2 3着色问题__eol____eol__ 12.3 8皇后问题__eol____eol__ 12.4 一般回溯法__eol____eol__ 12.5 分支限界法__eol____eol__ 12.6 练习__eol____eol__ 12.7 参考注释第13章 随机算法__eol____eol__ 13.1 引言__eol____eol__ 13.2 Las Vegas和Monte Carlo算法__eol____eol__ 13.3 两个简单的例子__eol____eol__ 13.4 随机快速排序__eol____eol__ 13.5 随机选择__eol____eol__ 13.6 占有问题__eol____eol__ 13.7 尾部界__eol____eol__ 13.8 Chernoff界的应用：多选__eol____eol__ 13.9 随机取样__eol____eol__ 13.10 最小割问题__eol____eol__ 13.11 测试串的相等性__eol____eol__ 13.12 模式匹配__eol____eol__ 13.13 素数测试__eol____eol__ 13.14 练习__eol____eol__ 13.15 参考注释第14章 近似算法__eol____eol__ 14.1 引言__eol____eol__ 14.2 基本定义__eol____eol__ 14.3 差界__eol____eol__ 14.4 相对性能界__eol____eol__ 14.5 多项式近似方案__eol____eol__ 14.6 完全多项式近似方案__eol____eol__ 14.7 练习__eol____eol__ 14.8 参考注释__eol____eol__第六部分 域指定问题的迭代改进第15章 网络流__eol____eol__ 15