算法设计与分析 Python案例详解·微课视频版

**篇 算 法 评 价 第1章 从理论看算法 …………………………………………………………………… 3 1.1 正确性 ………………………………………………………………………… 4 1.2 简单性 ……………………………………………………………………………… 6 1.3 时间复杂度分析 ……………………………………………………………… 6 1.3.1 非递归算法的分析方法 ……………………………………………… 8 1.3.2 递归算法的分析方法 ……………………………………………… 10 1.4 空间复杂度分析…………………………………………………………………… 14 1.5 *优性证明 …………………………………………………………………… 15 1.6 计算误差分析……………………………………………………………………… 16 1.6.1 误差分析基础 …………………………………………………………… 16 1.6.2 误差分析方法 …………………………………………………………… 21 1.7 NP完全理论 ………………………………………………………………… 23 1.7.1 计算模型 ………………………………………………………………… 24 1.7.2 P问题、NP问题和 NPC 问题 ………………………………………… 26 1.7.3 常见典型问题 …………………………………………………………… 27 1.8 小结 …………………………………………………………………………… 27 扩展阅读 ………………………………………………………………………………… 28 习题1 …………………………………………………………………………………… 29 第2章 从实践看算法 ………………………………………………………………… 30 2.1 性能测试方法……………………………………………………………………… 30 2.1.1 从零做测试 ……………………………………………………………… 30 2.1.2 工具介绍 ………………………………………………………………… 31 2.2 空间测试方法……………………………………………………………………… 33 2.2.1 Windows系统 …………………………………………………………… 33 2.2.2 Linux系统 ……………………………………………………………… 33 2.3 误差测试方法……………………………………………………………………… 36 2.3.1 计算 ULP ……………………………………………………………… 36 2.3.2 从零做测试 ……………………………………………………………… 36 Ⅳ 2.4 小结………………………………………………………………………………… 37 扩展阅读 ………………………………………………………………………………… 37 _x00B_习题2 …………………………………………………………………………………… 38 第二篇 算 法 设 计 第3章 递归 …………………………………………………………………………… 41 3.1 引例:阶乘 ………………………………………………………………………… 41 3.2 递归的基本思想 ……………………………………………………………… 42 3.3 递归应用:汉诺塔问题 ……………………………………………………… 42 3.4 递归应用:全排列 …………………………………………………………… 44 3.5 递归应用:整数划分 ………………………………………………………… 46 3.6 小结 …………………………………………………………………………… 47 扩展阅读 ………………………………………………………………………………… 47 习题3 …………………………………………………………………………………… 48 第4章 分治法 ………………………………………………………………………… 49 4.1 引例:寻找假币 ……………………………………………………………… 49 4.2 分治法基本思想 ……………………………………………………………… 51 4.2.1 分治法解题步骤 ………………………………………………………… 51 4.2.2 分治法适用条件 ………………………………………………………… 52 4.2.3 分治法代码框架 ………………………………………………………… 52 4.3 分治法应用:二分搜索 ……………………………………………………… 52 4.4 分治法应用:快速排序 …………………………………………………………… 56 4.5 分治法应用:归并排序 …………………………………………………………… 60 4.6 分治法应用:求*大*小项 ……………………………………………………… 63 4.7 分治法应用:棋盘覆盖 …………………………………………………………… 65 4.8 分治法应用:大整数乘法 …………………………………………………… 69 4.8.1 位乘法实现 ………………………………………………………… 69 4.8.2 分治法实现 ……………………………………………………………… 71 4.9 小结 …………………………………………………………………………… 72 扩展阅读 ………………………………………………………………………………… 73 习题4 …………………………………………………………………………………… 74 第5章 动态规划 ……………………………………………………………………… 75 5.1 引例一:兔子繁殖问题 ……………………………………………………… 75 5.2 引例二:数字三角形问题 …………………………………………………… 80 5.3 动态规划基本思想 …………………………………………………………… 83 5.3.1 动态规划与分治法的区别 ……………………………………………… 83 5.3.2 适合用动态规划求解的问题具有的两个重要性质 …………………… 83 Ⅴ 5.3.3 动态规划的解题步骤 …………………………………………………… 84 5.4 动态规划应用:0-1背包问题 ………………………………………………… 84 5.4.1 动态规划求解0-1背包问题 ………………………………………… 85 5.4.2 算法空间优化 ……………………………………………………… 91 5.5 动态规划应用:矩阵连乘问题 ……………………………………………… 94 5.6 动态规划应用:*长公共子序列 …………………………………………… 103 5.7 动态规划应用:*长不上升子序列 ………………………………………… 108 5.8 动态规划应用:编辑距离问题 ……………………………………………… 110 5.9 动态规划应用:*优二叉搜索树 …………………………………………… 113 5.10 小结 ………………………………………………………………………… 119 扩展阅读………………………………………………………………………………… 119 习题5…………………………………………………………………………………… 120 第6章 贪心法 ………………………………………………………………………… 121 6.1 引例:找零钱问题 …………………………………………………………… 121 6.2 贪心法的基本思想 ………………………………………………………… 122 6.3 贪心法应用:活动安排问题 ………………………………………………… 125 6.4 贪心法应用:过河问题 ……………………………………………………… 128 6.5 贪心法应用:哈夫曼编码 …………………………………………………… 130 6.6 贪心法应用:*小生成树 …………………………………………………… 135 6.7 贪心法应用:多机调度问题 ………………………………………………… 140 6.8 小结 ………………………………………………………………………… 141 扩展阅读………………………………………………………………………………… 141 习题6…………………………………………………………………………………… 143 第7章 回溯法 ………………………………………………………………………… 144 7.1 引例一:0-1背包问题 ……………………………………………………… 144 7.2 引例二:旅行售货员问题 …………………………………………………… 146 7.3 回溯法基本思想 ………………………………………………………………… 147 7.3.1 解题步骤 …………………………………………………………… 147 7.3.2 算法框架 …………………………………………………………… 148 7.4 回溯法应用:0-1背包问题 ………………………………………………… 149 7.5 回溯法应用:旅行售货员问题 ……………………………………………… 154 7.6 回溯法应用:符号三角形问题 ……………………………………………… 156 7.7 回溯法应用:n 皇后问题 …………………………………………………… 158 7.8 小结 ………………………………………………………………………… 162 扩展阅读………………………………………………………………………………… 163 _x00B_习题7…………………………………………………………………………………… 163 Ⅵ 第8章 分支限界法 …………………………………………………………………… 164 8.1 引例:0-1背包问题 ………………………………………………………… 164 8.2 分支限界法基本思想 ……………………………………………………… 166 8.3 分支限界法应用:0-1背包问题 …………………………………………… 167 8.4 分支限界法应用:旅行售货员问题 ………………………………………… 173 8.5 小结 ………………………………………………………………………… 175 扩展阅读………………………………………………………………………………… 175 习题8…………………………………………………………………………………… 176 第9章 概率算法 ……………………………………………………………………… 177 9.1 引例:主元素求解 …………………………………………………………… 177 9.2 概率算法的分类 ………………………………………………………………… 178 9.3 随机数生成 ……………………………………………………………………… 178 9.4 舍伍德算法 ………………………………………………………………… 179 9.5 拉斯维加斯算法 …………………………………………………………… 181 9.6 蒙特卡洛算法 ……………………………………………………………… 182 9.7 小结 ………………………………………………………………………… 183 扩展阅读………………………………………………………………………………… 184 习题9…………………………………………………………………………………… 184 第10章 综合应用 …………………………………………………………………… 185 10.1 算法设计策略的对比 …………………………………………………… 185 10.1.1 递归与分治法 ……………………………………………………… 185 10.1.2 动态规划与分治法 ………………………………………………… 186 10.1.3 动态规划与贪心法 ………………………………………………… 186 10.1.4 回溯法与分支限界法 ……………………………………………… 186 10.2 *大子段和问题 ………………………………………………………… 187 10.3 *短路径问题 …………………………………………………………… 195 10.3.1 单源*短路径 ………………………………………………… 195 10.3.2 所有点对间的*短路径 ……………………………………… 201 10.4 资源分配问题 …………………………………………………………… 204 10.5 小结 ……………………………………………………………………… 208 扩展阅读 ……………………………………………………………………………… 208 _x00B_习题10………………………………………………………………………………… 209 参考文献……………………………………………………………………………………… 210