算法详细说明四部曲*卷，详细说明算法基本，呈现算法实质 集斯坦福学校专家教授很多年课堂教学工作经验，从入门到精通，浅显易懂 算法是电子信息科学的关键与生命。算法的运用范畴极广，互联网路由器、测算基因组学、公钥数据加密学和数据库等的保持都必须算法。科学研究算法能够协助人们变成更出色的程序猿，能够我们一起具备更周密的逻辑思维，并取得成功解决各种各样场所的技术性招聘面试。
它是1本容易入门的算法新手入门书籍，它可做为程序猿的学习培训用书，也合适愿意学习培训算法和想提高算法思维逻辑的用户阅读文章。 这书包括以下几点： 渐进性剖析； 大O表示法； 主方式 ； 迅速分治算法； 随机化算法； 排序算法； 挑选算法。算法是电子信息科学行业*关键的根基之首。算法是程序流程的生命，只能把握了算法，能够轻轻松松地掌控软件开发。 算法详细说明系列产品书籍现有4卷，这书是第1卷——算法基本。
这书现有6章，关键详细介绍了4个主题风格，他们各自是渐进性剖析和大O表示法、分治算法和主方式 、随机化算法及其排列和挑选。附则A和附则B简易详细介绍了统计数据归纳法和离开几率的有关专业知识。这书的每章节均有小测试、章末练习题和程序编写题，这为用户的个人检查及其深化学习培训出示了较多的便捷。 这书为对算法很感兴趣的广大读者出示了丰富多彩而好用的材料，可以协助用户提高算法思维逻辑。这书合适计算机专科的高校老师和大学生，愿意塑造和训炼算法逻辑思维和计算思维的IT专业人员，及其在提前准备招聘面试的求职者和招聘者阅读文章参照。
目录
- 第 1章 绪论 1
- 1.1 为什么要学习算法 1
- 1.2 整数乘法 3
- 1.2.1 问题和解决方案 3
- 1.2.2 整数乘法问题 3
- 1.2.3 小学算法 4
- 1.2.4 操作数量的分析 5
- 1.2.5 还能做得更好吗 5
- 1.3 Karatsuba乘法 6
- 1.3.1 一个具体的例子 6
- 1.3.2 一种递归算法 7
- 1.3.3 Karatsuba乘法 9
- 1.4 MergeSort算法 11
- 1.4.1 推动力 11
- 1.4.2 排序 12
- 1.4.3 一个例子 13
- 1.4.4 伪码 14
- 1.4.5 Merge子程序 15
- 1.5 MergeSort算法分析 16
- 1.5.1 Merge的运行时间 17
- 1.5.2 MergeSort的运行时间 18
- 1.5.3 定理1.2的证明 19
- 1.5.4 小测验1.1～1.2的答案 23
- 1.6 算法分析的指导原则 23
- 1.6.1 第 1个原则：最坏情况分析 24
- 1.6.2 第 2个原则：全局分析 25
- 1.6.3 第3个原则：渐进性分析 26
- 1.6.4 什么是“快速”算法 27
- 1.7 本章要点 28
- 1.8 习题 29
- 挑战题 31
- 编程题 31
- 第 2章 渐进性表示法 32
- 2.1 要旨 32
- 2.1.1 推动力 32
- 2.1.2 高级思维 33
- 2.1.3 4个例子 34
- 2.1.4 小测验2.1～2.4的答案 38
- 2.2 大O表示法 40
- 2.2.1 文本定义 40
- 2.2.2 图形定义 40
- 2.2.3 数学定义 41
- 2.3 两个基本例子 42
- 2.3.1 k阶多项式是O(nk) 42
- 2.3.2 k阶多项式不是O(nk-1) 43
- 2.4 大Ω和大 表示法 44
- 2.4.1 大Ω表示法 44
- 2.4.2 大 表示法 45
- 2.4.3 小O表示法 46
- 2.4.4 渐进性表示法的来源 47
- 2.4.5 小测验2.5的答案 48
- 2.5 其他例子 48
- 2.5.1 在指数中添加一个常数 48
- 2.5.2 指数乘以一个常数 49
- 2.5.3 最大值vs.和 49
- 2.6 本章要点 50
- 2.7 习题 51
- 第3章 分治算法 53
- 3.1 分治法规范 53
- 3.2 以O(n log n)时间计数逆序对 54
- 3.2.1 问题 54
- 3.2.2 一个例子 54
- 3.2.3 协同筛选 55
- 3.2.4 穷举搜索法 55
- 3.2.5 分治法 56
- 3.2.6 高级算法 57
- 3.2.7 关键思路：站在MergeSort的肩膀上 57
- 3.2.8 重温Merge 58
- 3.2.9 Merge和分离逆序对 60
- 3.2.10 Merge_and_CountSplitInv 61
- 3.2.11 正确性 61
- 3.2.12 运行时间 62
- 3.2.13 小测验3.1～3.2的答案 62
- 3.3 Strassen的矩阵相乘算法 63
- 3.3.1 矩阵相乘 63
- 3.3.2 例子（n = 2） 64
- 3.3.3 简单算法 64
- 3.3.4 分治法 65
- 3.3.5 节省一个递归调用 67
- 3.3.6 细节 68
- 3.3.7 小测验3.3的答案 69
- *3.4 O(n log n)时间的最近点对（Closest Pair）算法 70
- 3.4.1 问题 70
- 3.4.2 热身：1D情况 71
- 3.4.3 预处理 71
- 3.4.4 一种分治方法 72
- 3.4.5 一个微妙的变化 74
- 3.4.6 ClosestSplitPair 74
- 3.4.7 正确性 76
- 3.4.8 辅助结论3.3（a）的证明 77
- 3.4.9 辅助结论3.3（b）的证明 78
- 3.4.10 小测验3.4的答案 80
- 3.5 本章要点 80
- 3.6 习题 81
- 挑战题 81
- 编程题 82
- 第4章 主方法 83
- 4.1 重温整数乘法 83
- 4.1.1 RecIntMult算法 84
- 4.1.2 Karatsuba算法 84
- 4.1.3 比较递归过程 85
- 4.2 形式声明 86
- 4.2.1 标准递归过程 86
- 4.2.2 主方法的陈述和讨论 87
- 4.3 6个例子 88
- 4.3.1 重温MergeSort 89
- 4.3.2 二分搜索 89
- 4.3.3 整数乘法的递归算法 90
- 4.3.4 Karatsuba乘法 90
- 4.3.5 矩阵乘法 91
- 4.3.6 一个虚构的递归过程 92
- 4.3.7 小测验4.2～4.3的答案 93
- *4.4 主方法的证明 94
- 4.4.1 前言 94
- 4.4.2 重温递归树 95
- 4.4.3 单层所完成的工作 96
- 4.4.4 各层累计 97
- 4.4.5 正义与邪恶：需要考虑3种情况 98
- 4.4.6 预告运行时间上界 99
- 4.4.7 最后的计算：第 一种情况 100
- 4.4.8 迂回之旅：几何级数 101
- 4.4.9 最后的计算：第二种情况和第三种情况 102
- 4.4.10 小测验4.4～4.5的答案 103
- 4.5 本章要点 103
- 4.6 习题 104
- 第5章 快速排序（QuickSort） 107
- 5.1 概述 107
- 5.1.1 排序 108
- 5.1.2 根据基准元素进行划分 108
- 5.1.3 高级描述 110
- 5.1.4 内容前瞻 110
- 5.2 围绕基准元素进行划分 111
- 5.2.1 简易方法 111
- 5.2.2 原地实现：高级计划 112
- 5.2.3 例子 113
- 5.2.4 Partition子程序的伪码 115
- 5.2.5 QuickSort的伪码 117
- 5.3 良好的基准元素的重要性 117
- 5.3.1 ChoosePivot的简单实现 118
- 5.3.2 ChoosePivot的过度实现 118
- 5.3.3 小测验5.1～5.2的答案 119
- 5.4 随机化的QuickSort 121
- 5.4.1 ChoosePivot的随机化实现 121
- 5.4.2 随机化QuickSort的运行时间 122
- 5.4.3 直觉：随机基准元素为什么很好 123
- *5.5 随机化QuickSort的分析 124
- 5.5.1 预备工作 125
- 5.5.2 分解蓝图 126
- 5.5.3 应用蓝图 128
- 5.5.4 计算比较的概率 130
- 5.5.5 最后的计算 132
- 5.5.6 小测验5.3的答案 133
- *5.6 排序需要 (n log n)的比较 134
- 5.6.1 基于比较的排序算法 134
- 5.6.2 具有更强前提的更快速排序 135
- 5.6.3 定理5.5的证明 136
- 5.7 本章要点 138
- 5.8 习题 139
- 挑战题 140
- 编程题 141
- 第6章 线性时间级的选择 142
- 6.1 RSelect算法 143
- 6.1.1 选择问题 143
- 6.1.2 简化为排序 144
- 6.1.3 分治法 145
- 6.1.4 RSelect的伪码 146
- 6.1.5 RSelect的运行时间 147
- 6.1.6 小测验6.1～6.2的答案 149
- *6.2 RSelect的分析 150
- 6.2.1 根据阶段追踪进展 150
- 6.2.2 简化为掷硬币 151
- 6.2.3 综合结论 153
- *6.3 DSelect算法 154
- 6.3.1 基本思路：中位的中位元素 154
- 6.3.2 DSelect的伪码 155
- 6.3.3 理解DSelect 156
- 6.3.4 DSelect的运行时间 157
- *6.4 DSelect的分析 159
- 6.4.1 递归调用之外所完成的工作 159
- 6.4.2 一个粗略的递归过程 159
- 6.4.3 30-70辅助结论 160
- 6.4.4 解析递归过程 163
- 6.4.5 先猜后验方法 164
- 6.5 本章要点 166
- 6.6 本章习题 166
- 挑战题 167
- 编程题 168
- 附录A 快速回顾数学归纳法 169
- 附录B 快速回顾离散概率 173
