第1部分 算法和算法分析__eol__第1章 算法问题求解基础 1__eol__1.1 算法概述 1__eol__1.1.1 什么是算法 1__eol__1.1.2 为什么学习算法 3__eol__1.2 问题求解方法 3__eol__1.2.1 问题和问题求解 4__eol__1.2.2 问题求解过程 4__eol__1.2.3 软件生命周期 5__eol__1.3 算法设计与分析 5__eol__1.3.1 算法问题求解过程 5__eol__1.3.2 如何设计算法 6__eol__1.3.3 如何表示算法 6__eol__1.3.4 如何确认算法 6__eol__1.3.5 如何分析算法 7__eol__1.4 递归和归纳 7__eol__1.4.1 递归 7__eol__1.4.2 递归算法示例 9__eol__1.4.3 归纳证明 11__eol__习题1 13__eol__第2章 算法分析基础 14__eol__2.1 算法复杂度 14__eol__2.1.1 什么是好的算法 14__eol__2.1.2 影响程序执行时间的因素 15__eol__2.1.3 算法的时间复杂度 16__eol__2.1.4 使用程序步分析算法 17__eol__2.1.5 算法的空间复杂度 18__eol__2.2 渐近表示法 19__eol__2.2.1 大O记号 19__eol__2.2.2 Ω记号 20__eol__2.2.3 Θ记号 21__eol__2.2.4 小o记号 21__eol__2.2.5 算法按时间复杂度分类 21__eol__2.3 递推关系 22__eol__2.3.1 递推方程 22__eol__2.3.2 替换方法 23__eol__2.3.3 迭代方法 23__eol__2.3.4 递归树 23__eol__2.3.5 主方法 25__eol__2.4 分摊分析 25__eol__2.4.1 聚集分析 26__eol__2.4.2 会计方法 26__eol__2.4.3 势能方法 27__eol__习题2 28__eol__第3章 伸展树与跳表 31__eol__3.1 伸展树 31__eol__3.1.1 二叉搜索树 31__eol__3.1.2 自调节树和伸展树 31__eol__3.1.3 伸展操作 32__eol__3.1.4 伸展树类 34__eol__3.1.5 旋转的实现 34__eol__3.1.6 插入运算的实现 35__eol__3.1.7 分摊分析 37__eol__3.2 跳表 39__eol__3.2.1 什么是跳表 39__eol__3.2.2 跳表类 40__eol__3.2.3 层次分配 42__eol__3.2.4 插入运算的实现 43__eol__3.2.5 性能分析 44__eol__习题3 45__eol__ __eol__第2部分 算法设计策略__eol__ __eol__第4章 基本搜索和遍历方法 46__eol__4.1 基本概念 46__eol__4.2 图的搜索和遍历 47__eol__4.2.1 搜索方法 47__eol__4.2.2 邻接表类 48__eol__4.2.3 广度优先搜索 49__eol__4.2.4 深度优先搜索 51__eol__4.3 双连通分量 53__eol__4.3.1 基本概念 53__eol__4.3.2 发现关节点 54__eol__4.3.3 构造双连通图 58__eol__4.4 与或图 58__eol__4.4.1 问题分解 58__eol__4.4.2 判断与或树是否可解 60__eol__4.4.3 构建解树 61__eol__4.5 区间最值查询（RMQ） 62__eol__4.5.1 区间信息维护与查询 62__eol__4.5.2 ST算法求解RMQ问题 63__eol__4.6 最近公共祖先（LCA） 65__eol__4.6.1 概述 65__eol__4.6.2 倍增法求解LCA问题 66__eol__4.6.3 在线RMQ法求解LCA问题 68__eol__4.6.4 Tarjan算法求解LCA问题 70__eol__习题4 73__eol__第5章 分治法 75__eol__5.1 一般方法 75__eol__5.1.1 分治法的基本思想 75__eol__5.1.2 算法分析 76__eol__5.1.3 数据结构 77__eol__5.2 求最大、最小元 78__eol__5.2.1 分治法求解 78__eol__5.2.2 时间分析 79__eol__5.3 二分搜索 80__eol__5.3.1 分治法求解 80__eol__5.3.2 对半搜索 81__eol__5.3.3 二叉判定树 82__eol__5.3.4 搜索算法的时间下界 84__eol__5.4 排序问题 85__eol__5.4.1 合并排序 85__eol__5.4.2 快速排序 87__eol__5.4.3 排序算法的时间下界 91__eol__5.5 选择问题 92__eol__5.5.1 分治法求解 92__eol__5.5.2 随机选择主元 93__eol__5.5.3 线性时间选择算法 94__eol__5.5.4 时间分析 96__eol__5.5.5 允许重复元素的选择算法 97__eol__5.6 斯特拉森矩阵乘法 97__eol__5.6.1 分治法求解 97__eol__5.6.2 斯特拉森矩阵乘法简介 98__eol__习题5 99__eol__第6章 贪心法 102__eol__6.1 一般方法 102__eol__6.2 背包问题 103__eol__6.2.1 问题描述 103__eol__6.2.2 贪心法求解 104__eol__6.2.3 算法正确性 105__eol__6.3 带时限的作业排序问题 106__eol__6.3.1 问题描述 106__eol__6.3.2 贪心法求解 107__eol__6.3.3 算法正确性 108__eol__6.3.4 可行性判定 108__eol__6.3.5 作业排序贪心算法 109__eol__6.3.6 改进算法 110__eol__6.4 最佳合并模式 112__eol__6.4.1 问题描述 113__eol__6.4.2 贪心法求解 113__eol__6.4.3 算法正确性 115__eol__6.5 最小代价生成树 116__eol__6.5.1 问题描述 116__eol__6.5.2 贪心法求解 116__eol__6.5.3 普里姆算法 117__eol__6.5.4 克鲁斯卡尔算法 119__eol__6.5.5 算法正确性 121__eol__6.6 单源最短路径 122__eol__6.6.1 问题描述 122__eol__6.6.2 贪心法求解 122__eol__6.6.3 迪杰斯特拉算法 123__eol__6.6.4 算法正确性 125__eol__6.7 磁带最优存储 127__eol__6.7.1 单带最优存储 127__eol__6.7.2 多带最优存储 128__eol__6.8 贪心法的基本要素 129__eol__6.8.1 最优量度标准 129__eol__6.8.2 最优子结构 129__eol__习题6 130__eol__第7章 动态规划法 133__eol__7.1 一般方法和基本要素 133__eol__7.1.1 一般方法 133__eol__7.1.2 基本要素 134__eol__7.1.3 多段图问题 134__eol__7.1.4 资源分配问题 137__eol__7.1.5 关键路径问题 138__eol__7.2 每对结点间的最短路径 140__eol__7.2.1 问题描述 140__eol__7.2.2 动态规划法求解 140__eol__7.2.3 弗洛伊德算法 141__eol__7.2.4 算法正确性 143__eol__7.3 矩阵连乘 143__eol__7.3.1 问题描述 143__eol__7.3.2 动态规划法求解 144__eol__7.3.3 矩阵连乘算法 145__eol__7.3.4 备忘录方法 147__eol__7.4 最长公共子序列 147__eol__7.4.1 问题描述 147__eol__7.4.2 动态规划法求解 148__eol__7.4.3 最长公共子序列算法 149__eol__7.4.4 改进算法 151__eol__7.5 最优二叉搜索树 151__eol__7.5.1 问题描述 151__eol__7.5.2 动态规划法求解 151__eol__7.5.3 最优二叉搜索树算法 153__eol__7.6 0/1背包问题 155__eol__7.6.1 问题描述 155__eol__7.6.2 动态规划法求解 155__eol__7.6.3 0/1背包问题算法框架 157__eol__7.6.4 0/1背包问题算法 160__eol__7.6.5 性能分析 162__eol__7.6.6 使