算法详解（卷1）——算法基础

作者简介

蒂姆·拉夫加登Tim Roughgarden是斯坦福大学计算机科学系的教授,也是该校管理科学和工程系的客座教授，他从2004年开始教授和研究算法。本书是他的算法详解四部曲的第一卷，基于他从2012年开始定期举行的在线算法课程编写。

本书目录

第1章 绪论 1
1.1 为什么要学习算法 1
1.2 整数乘法 3
问题和解决方案 3
整数乘法问题 3
小学算法 4
操作数量的分析 5
还能做得更好吗 5
1.3 Karatsuba乘法 6
一个具体的例子 6
一种递归算法 7
Karatsuba乘法 9
1.4 MergeSort算法 11
推动力 11
排序 12
一个例子 13
伪码 14
Merge子程序 15
1.5 MergeSort算法分析 16
Merge的运行时间 17
MergeSort的运行时间 18
定理1.2的证明 19
小测验1.1～1.2的答案 23
1.6 算法分析的指导原则 23
第1个原则：最坏情况分析 24
第2个原则：全局分析 25
第3个原则：渐进性分析 26
什么是“快速”算法 27
1.7 本章要点 28
1.8 习题 29
挑战题 31
编程题 31
第2章 渐进性表示法 32
2.1 要旨 32
推动力 32
高级思维 33
4个例子 34
小测验2.1～2.4的答案 38
2.2 大O表示法 40
文本定义 40
图形定义 40
数学定义 41
2.3 两个基本例子 42
k阶多项式是Onk 42
k阶多项式不是Onk-1 43
2.4 大Ω和大表示法 44
大Ω表示法 44
大表示法 45
小O表示法 46
渐进性表示法的来源 47
小测验2.5的答案 48
2.5 其他例子 48
在指数中添加一个常数 48
指数乘以一个常数 49
最大值vs.和 49
2.6 本章要点 50
2.7 习题 51
第3章 分治算法 53
3.1 分治法规范 53
3.2 以On log n时间计数逆序对 54
问题 54
一个例子 54
协同筛选 55
穷举搜索法 55
分治法 56
高级算法 57
关键思路：站在MergeSort的肩膀上 57
重温Merge 58
Merge和分离逆序对 60
Merge_and_CountSplitInv 61
正确性 61
运行时间 62
小测验3.1～3.2的答案 62
3.3 Strassen的矩阵相乘算法 63
矩阵相乘 63
例子n = 2 64
简单算法 64
分治法 65
节省一个递归调用 67
细节 68
小测验3.3的答案 69
*3.4 On log n时间的最近点对Closest Pair算法 70
问题 70
热身：1D情况 71
预处理 71
一种分治方法 72
一个微妙的变化 74
ClosestSplitPair 74
正确性 76
辅助结论3.3a的证明 77
辅助结论3.3b的证明 78
小测验3.4的答案 80
3.5 本章要点 80
3.6 习题 81
挑战题 81
编程题 82
第4章 主方法 83
4.1 重温整数乘法 83
RecIntMult算法 84
Karatsuba算法 84
比较递归过程 85
4.2 形式声明 86
标准递归过程 86
主方法的陈述和讨论 87
4.3 6个例子 88
重温MergeSort 89
二分搜索 89
整数乘法的递归算法 90
Karatsuba乘法 90
矩阵乘法 91
一个虚构的递归过程 92
小测验4.2～4.3的答案 93
*4.4 主方法的证明 94
前言 94
重温递归树 95
单层所完成的工作 96
各层累计 97
正义与邪恶：需要考虑3种情况 98
预告运行时间上界 99
最后的计算：第一种情况 100
迂回之旅：几何级数 101
最后的计算：第二种情况和第三种情况 102
小测验4.4～4.5的答案 103
4.5 本章要点 103
4.6 习题 104
第5章 快速排序QuickSort 107
5.1 概述 107
排序 108
根据基准元素进行划分 108
高级描述 110
内容前瞻 110
5.2 围绕基准元素进行划分 111
简易方法 111
原地实现：高级计划 112
例子 113
Partition子程序的伪码 115
QuickSort的伪码 117
5.3 良好的基准元素的重要性 117
ChoosePivot的简单实现 118
ChoosePivot的过度实现 118
小测验5.1～5.2的答案 119
5.4 随机化的QuickSort 121
ChoosePivot的随机化实现 121
随机化QuickSort的运行时间 122
直觉：随机基准元素为什么很好 123
*5.5 随机化QuickSort的分析 124
预备工作 125
分解蓝图 126
应用蓝图 128
计算比较的概率 130
最后的计算 132
小测验5.3的答案 133
*5.6 排序需要  n log n的比较 134
基于比较的排序算法 134
具有更强前提的更快速排序 135
定理5.5的证明 136
5.7 本章要点 138
5.8 习题 139
挑战题 140
编程题 141
第6章 线性时间级的选择 142
6.1 RSelect算法 143
选择问题 143
简化为排序 144
分治法 145
RSelect的伪码 146
RSelect的运行时间 147
小测验6.1～6.2的答案 149
*6.2 RSelect的分析 150
根据阶段追踪进展 150
简化为掷硬币 151
综合结论 153
*6.3 DSelect算法 154
基本思路：中位的中位元素 154
DSelect的伪码 155
理解DSelect 156
DSelect的运行时间 157
*6.4 DSelect的分析 159
递归调用之外所完成的工作 159
一个粗略的递归过程 159
30-70辅助结论 160
解析递归过程 163
先猜后验方法 164
6.5 本章要点 166
6.6 本章习题 166
挑战题 167
编程题 168
附录A 快速回顾数学归纳法 169
附录B 快速回顾离散概率 173
· · · · · ·