实例介绍
【实例简介】
【实例截图】
【核心代码】
目录 序（一） iii 序（二） iv 前言 i 第一章 绪论 2 1.1 什么是算法问题？ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.2 怎样进行算法设计？ . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.2.1 观察问题内在结构的途径 . . . . . . . . . . . . . . . . . . . . . 5 1.2.2 “分而治之”算法设计过程简介 . . . . . . . . . . . . . . . . . . . 7 1.2.3 “逐步改进”算法设计过程简介 . . . . . . . . . . . . . . . . . . . 10 1.2.4 智能枚举算法设计过程简介 . . . . . . . . . . . . . . . . . . . . 12 1.3 算法的复杂度 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 1.3.1 时间复杂度与空间复杂度 . . . . . . . . . . . . . . . . . . . . . 21 1.3.2 大 O 记号 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 第二章 “分而治之”算法 27 2.1 引言 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 2.2 排序问题：对数组的归约 . . . . . . . . . . . . . . . . . . . . . . . . . 28 2.2.1 依据元素下标拆分数组：插入排序与归并排序 . . . . . . . . . . 28 2.2.2 “分而治之”算法时间复杂度分析及 Master 定理 . . . . . . . . . 34 2.2.3 依据元素的值拆分数组：QuickSort 算法 . . . . . . . . . . . 36 2.3 一个密切相关的问题：数组中的逆序对计数 . . . . . . . . . . . . . . . 44 2.4 选择问题：对数组的归约 . . . . . . . . . . . . . . . . . . . . . . . . . 47 v vi 目录 2.4.1 采用随机选择的一个元素作中心元 . . . . . . . . . . . . . . . . 48 2.4.2 依据随机样本的统计量确定中心元 . . . . . . . . . . . . . . . . 50 2.4.3 选择“分组中位数的中位数”作为中心元 . . . . . . . . . . . . . . 52 2.5 整数乘法：对一对数组的归约 . . . . . . . . . . . . . . . . . . . . . . . 55 2.6 快速傅里叶变换：对数组的归约 . . . . . . . . . . . . . . . . . . . . . 62 2.7 矩阵乘法：对二维数组的归约 . . . . . . . . . . . . . . . . . . . . . . . 71 2.8 平面上最近点对寻找问题：对点集的归约 . . . . . . . . . . . . . . . . 73 第三章 动态规划算法 81 3.1 引言 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81 3.2 矩阵序列的链式相乘问题：对序列的归约 . . . . . . . . . . . . . . . . 82 3.2.1 算法设计：一个比较慢的初始版本 . . . . . . . . . . . . . . . . 83 3.2.2 算法设计：改进后的版本 . . . . . . . . . . . . . . . . . . . . . 87 3.2.3 算法运行过程示例 . . . . . . . . . . . . . . . . . . . . . . . . . 89 3.2.4 时间复杂度分析 . . . . . . . . . . . . . . . . . . . . . . . . . . 92 3.2.5 一些讨论 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92 3.3 动态规划与多步决策过程 . . . . . . . . . . . . . . . . . . . . . . . . . 93 3.4 0 − 1 背包问题：对集合的归约 . . . . . . . . . . . . . . . . . . . . . . 95 3.4.1 算法设计：一个比较慢的初始版本 . . . . . . . . . . . . . . . . 95 3.4.2 算法设计：改进后的版本 . . . . . . . . . . . . . . . . . . . . . 97 3.4.3 算法运行过程示例 . . . . . . . . . . . . . . . . . . . . . . . . . 98 3.4.4 时间复杂度分析 . . . . . . . . . . . . . . . . . . . . . . . . . . 99 3.4.5 一些讨论 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100 3.5 RNA 二级结构预测：对字符串的归约 . . . . . . . . . . . . . . . . . . 101 3.5.1 算法设计与描述 . . . . . . . . . . . . . . . . . . . . . . . . . . 103 3.5.2 算法运行过程示例 . . . . . . . . . . . . . . . . . . . . . . . . . 104 3.5.3 时间复杂度分析 . . . . . . . . . . . . . . . . . . . . . . . . . . 105 3.6 隐马尔可夫模型的解码问题：对序列的归约 . . . . . . . . . . . . . . . 106 3.6.1 算法设计与描述 . . . . . . . . . . . . . . . . . . . . . . . . . . 108 3.6.2 算法运行过程示例 . . . . . . . . . . . . . . . . . . . . . . . . . 110 3.6.3 时间复杂度分析 . . . . . . . . . . . . . . . . . . . . . . . . . . 110 3.6.4 关于子问题定义的讨论 . . . . . . . . . . . . . . . . . . . . . . 111 目录 vii 3.7 字符串间的编辑距离：对一对字符串的归约 . . . . . . . . . . . . . . . 112 3.7.1 算法设计与描述 . . . . . . . . . . . . . . . . . . . . . . . . . . 115 3.7.2 算法运行过程示例 . . . . . . . . . . . . . . . . . . . . . . . . . 117 3.7.3 时间复杂度分析 . . . . . . . . . . . . . . . . . . . . . . . . . . 119 3.7.4 一些讨论 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119 3.8 字符串局部联配：对一对字符串的归约 . . . . . . . . . . . . . . . . . . 119 3.8.1 算法设计与描述 . . . . . . . . . . . . . . . . . . . . . . . . . . 121 3.8.2 算法运行过程实例 . . . . . . . . . . . . . . . . . . . . . . . . . 123 3.8.3 时间复杂度分析 . . . . . . . . . . . . . . . . . . . . . . . . . . 125 3.8.4 一些讨论 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125 3.9 树上的顶点覆盖问题：对树的归约 . . . . . . . . . . . . . . . . . . . . 126 3.9.1 算法设计 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127 3.9.2 时间复杂度分析 . . . . . . . . . . . . . . . . . . . . . . . . . . 127 3.9.3 算法设计：更“细”的子问题表述方式 . . . . . . . . . . . . . . . 128 3.10 有向无环图上的单源最短路径：对图的归约 . . . . . . . . . . . . . . . 129 3.10.1 算法设计与描述 . . . . . . . . . . . . . . . . . . . . . . . . . . 130 3.10.2 时间复杂度分析 . . . . . . . . . . . . . . . . . . . . . . . . . . 133 3.11 一般有向图上的单源最短路径：对图的归约 . . . . . . . . . . . . . . . 133 3.11.1 算法设计与描述 . . . . . . . . . . . . . . . . . . . . . . . . . . 134 3.11.2 算法运行过程示例 . . . . . . . . . . . . . . . . . . . . . . . . . 136 3.11.3 时间复杂度分析 . . . . . . . . . . . . . . . . . . . . . . . . . . 137 3.11.4 一些讨论 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137 3.12 应用动态规划技术求解整数规划问题 . . . . . . . . . . . . . . . . . . . 138 3.12.1 算法设计与描述 . . . . . . . . . . . . . . . . . . . . . . . . . . 139 3.12.2 算法运行过程示例 . . . . . . . . . . . . . . . . . . . . . . . . . 141 3.12.3 时间复杂度分析 . . . . . . . . . . . . . . . . . . . . . . . . . . 141 3.12.4 一些讨论 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141 3.13 动态规划与马尔可夫决策过程 . . . . . . . . . . . . . . . . . . . . . . . 143 3.13.1 算法设计与描述 . . . . . . . . . . . . . . . . . . . . . . . . . . 144 3.13.2 运行过程示例 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145 3.13.3 一些讨论 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146 viii 目录 第四章 高级动态规划 157 4.1 引言 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157 4.2 降低空间复杂度：以“算”代“存” . . . . . . . . . . . . . . . . . . . . . . 158 4.2.1 计算最优决策项的分而治之策略 . . . . . . . . . . . . . . . . . 159 4.2.2 将最优决策项的计算融入最优解值的计算 . . . . . . . . . . . . 163 4.3 降低空间复杂度：以“存函数”代替“存值” . . . . . . . . . . . . . . . . . 165 4.4 降低时间复杂度：利用子问题最优解值的稀疏性 . . . . . . . . . . . . 170 4.4.1 利用稀疏性加速动态规划算法 . . . . . . . . . . . . . . . . . . . 170 4.4.2 只与边界点比较以进一步加速 . . . . . . . . . . . . . . . . . . . 173 4.4.3 一些讨论 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 177 4.5 降低时间复杂度：基于最优解估计值的去冗余技术 . . . . . . . . . . . 177 4.5.1 计算两序列编辑距离的 Ficket 算法 . . . . . . . . . . . . . . . 177 4.5.2 改进版本：条带型动态规划算法 . . . . . . . . . . . . . . . . . 179 4.6 降低时间复杂度：利用单调性的动态规划 . . . . . . . . . . . . . . . . 180 4.7 降低时间复杂度：QI . . . . . . . . . . . . . . . . . . . . . . . . . . . . 180 第五章 贪心算法 183 5.1 引言 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 183 5.2 区间调度问题的两个版本：动态规划与贪心算法 . . . . . . . . . . . . 184 5.2.1 求解区间调度问题的动态规划算法 . . . . . . . . . . . . . . . . 184 5.2.2 区间调度问题的特殊情形及贪心求解算法 . . . . . . . . . . . . 186 5.2.3 关于贪心规则设计过程的一些讨论 . . . . . . . . . . . . . . . . 189 5.3 无负边有向图上的单源最短路径问题 . . . . . . . . . . . . . . . . . . . 190 5.3.1 Bellman-Ford 算法中的第一类冗余计算 . . . . . . . . . . . 191 5.3.2 改进的 Bellman-Ford 算法 . . . . . . . . . . . . . . . . . . . 193 5.3.3 Bellman-Ford 算法中的第二类冗余计算 . . . . . . . . . . . 193 5.3.4 进一步的改进：Dijkstra 贪心算法 . . . . . . . . . . . . . . . 194 5.3.5 一些讨论 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 195
好例子网口号：伸出你的我的手 — 分享！
相关软件
小贴士
感谢您为本站写下的评论，您的评论对其它用户来说具有重要的参考价值，所以请认真填写。
- 类似“顶”、“沙发”之类没有营养的文字，对勤劳贡献的楼主来说是令人沮丧的反馈信息。
- 相信您也不想看到一排文字/表情墙，所以请不要反馈意义不大的重复字符，也请尽量不要纯表情的回复。
- 提问之前请再仔细看一遍楼主的说明，或许是您遗漏了。
- 请勿到处挖坑绊人、招贴广告。既占空间让人厌烦，又没人会搭理，于人于己都无利。
关于好例子网
本站旨在为广大IT学习爱好者提供一个非营利性互相学习交流分享平台。本站所有资源都可以被免费获取学习研究。本站资源来自网友分享，对搜索内容的合法性不具有预见性、识别性、控制性，仅供学习研究，请务必在下载后24小时内给予删除，不得用于其他任何用途，否则后果自负。基于互联网的特殊性，平台无法对用户传输的作品、信息、内容的权属或合法性、安全性、合规性、真实性、科学性、完整权、有效性等进行实质审查；无论平台是否已进行审查，用户均应自行承担因其传输的作品、信息、内容而可能或已经产生的侵权或权属纠纷等法律责任。本站所有资源不代表本站的观点或立场，基于网友分享，根据中国法律《信息网络传播权保护条例》第二十二与二十三条之规定，若资源存在侵权或相关问题请联系本站客服人员，点此联系我们。关于更多版权及免责申明参见 版权及免责申明
网友评论
我要评论