算法设计与分析

本书以算法设计策略为知识单元，系统地介绍了算法设计与分析的概念和方法。全书内容包括算法的基本概念、排序及并查集算法、递归与分治策略、贪婪算法、动态规划算法、回溯法、分支与限界法、随机算法、NP完全问题等。本书从一些经典问题入手，分析如何求解问题，然后使用伪代码对问题的算法进行描述，最后对算法的时间复杂度进行分析。为了便于读者学习和实践，本书采用C语言对算法进行描述，可读性强。每章内容后附有习题，便于读者复习巩固。 本书可作为高等院校计算机专业本科生和研究生的教材，也可作为希望进行算法学习和研究的相关人员的参考资料。

无

第1章 算法的基本概念 1.1 算法的定义和特征 1 1.2 算法复杂性分析 3 1.3 渐进记号 5 1.4 最好情况、最坏情况和平均情况分析 10 1.5 递归算法分析 14 习题 20 第2章 排序及并查集算法 2.1 冒泡排序 24 2.2 选择排序 25 2.3 合并排序 26 2.3.1 merge算法 26 2.3.2 合并排序算法的具体内容 27 2.3.3 合并排序算法分析 30 2.4 堆及堆排序 30 2.4.1 堆的概念及性质 31 2.4.2 堆的操作 32 2.4.3 堆排序 39 2.4.4 堆排序的应用 40 2.5 桶排序 41 2.5.1 桶排序的基本步骤 41 2.5.2 桶排序的时间复杂度 43 2.6 基数排序 44 2.6.1 基数排序的基本思想 44 2.6.2 基数排序算法的实现 45 2.6.3 基数排序算法的合理性证明 47 2.6.4 基数排序的复杂度分析 47 2.6.5 基数排序的应用 48 2.7 并查集算法 48 习题 52 第3章 递归与分治 3.1 递归算法 54 3.1.1 递归算法的基本思想 55 3.1.2 递归算法实例 55 3.2 分治法 60 3.2.1 分治法的基本思想 60 3.2.2 分治法的步骤 63 3.2.3 应用分治法进行合并排序 64 3.2.4 快速排序 66 3.2.5 快速排序的改进 70 3.2.6 平面最近点对问题 71 3.2.7 BFPRT算法（TOP-K问题） 81 3.2.8 棋盘覆盖问题 84 习题 87 第4章 贪婪法 4.1 贪婪算法 89 4.2 贪婪法的设计思想 92 4.3 区间调度问题 92 4.4 背包问题的贪婪算法 94 4.5 狄斯奎诺(Dijkstra)算法 97 4.5.1 狄斯奎诺算法的核心原理 97 4.5.2 狄斯奎诺算法的步骤描述 99 4.5.3 狄斯奎诺算法的实现 101 4.5.4 狄斯奎诺算法的不足 105 4.6 数列极差问题 106 4.6.1 问题分析 106 4.6.2 极差问题的算法设计 107 4.6.3 极差问题的时间和空间复杂度分析 108 4.7 分数转化问题 108 4.8 被3整除的元素最大和问题 110 4.9 跳跃游戏问题 111 习题 114 第5章 动态规划 5.1 动态规划基本概述 116 5.1.1 动态规划的基本术语 118 5.1.2 动态规划数学模型建立的一般步骤 121 5.2 动态规划的基本性质 123 5.3 货郎担问题 124 5.4 多段图最短路径问题 127 5.4.1 多段图的计算过程 128 5.4.2 多段图的动态规划算法实现 129 5.5 设备更新问题 131 5.6 最长公共子序列 134 5.6.1 最长公共子序列的搜索过程 135 5.6.2 最长公共子序列算法实现 137 5.7 0/1背包问题 139 5.7.1 0/1背包问题求解分析 140 5.7.2 0/1背包问题的实现 141 5.8 最大连续子序列和问题 143 5.9 最优二叉搜索树 145 5.9.1 OBST问题的动态规划求解过程 147 5.9.2 OBST问题的实现过程 149 习题 151 第6章 回溯 6.1 问题的解空间和状态空间树 153 6.2 状态空间树的动态搜索 154 6.3 回溯算法的一般性描述 157 6.4 图的着色问题 160 6.4.1 图着色问题的求解过程分析 161 6.4.2 图着色问题算法实现 163 6.5 n皇后问题 165 6.5.1 n皇后问题的求解过程分析 165 6.5.2 n皇后问题的求解实现 166 6.5.3 数独问题 168 6.6 一些经典算法的回溯求解 172 习题 182 第7章 分支与限界 7.1 分支与限界算法 184 7.2 作业分配问题 186 7.2.1 分支限界法解作业分配问题的思想方法 186 7.2.2 分支限界法解作业分配问题算法的实现 188 7.3 单源最短路径问题 192 7.3.1 分支限界法解单源最短路径问题的思想方法 192 7.3.2 分支限界法解单源最短路径问题算法的实现 194 7.4 0/1背包问题 197 7.4.1 分支限界法解0/1背包问题的思想方法 197 7.4.2 0/1背包问题分支限界算法的实现 200 7.5 货郎担问题 204 7.5.1 费用矩阵的特性及归约 204 7.5.2 分支限界法解最短汉密尔顿回路的思想 205 7.5.3 货郎担问题的求解过程 208 7.5.4 几个辅助函数的实现 212 7.5.5 货郎担问题分支限界算法的实现 217 习题 219 第8章 随机算法 8.1 随机化算法 222 8.1.1 为什么要随机化 222 8.1.2 随机算法 222 8.2 随机数发生器 223 8.3 数值概率算法 225 8.4 拉斯维加斯算法 229 8.4.1 随机快速排序算法 230 8.4.2 随机选择算法 231 8.4.3 n皇后问题的随机算法 232 8.4.4 随机字符串匹配算法 234 8.4.5 整数因子 239 8.5 蒙特卡罗算法 242 8.5.1 函数极大值估计问题 243 8.5.2 主元素问题 244 8.5.3 素数测试问题 246 8.6 随机算法的应用 251 习题 252 第9章 NP完全问题 9.1 判定问题和优化问题 254 9.2 P类问题和NP类问题 255 9.3 NP完全问题 260 习题 262 参考文献