前言

致谢

关于本书

第1章 算法简介1

1.1引言1

1.1.1性能方面1

1.1.2问题解决技巧2

1.2二分查找2

1.2.1更佳的查找方式4

1.2.2运行时间8

1.3大O 表示法8

1.3.1算法的运行时间以不同的速度增加9

1.3.2理解不同的大O运行时间10

1.3.3大O 表示法指出了最糟情况下的运行时间12

1.3.4一些常见的大O运行时间12

1.3.5旅行商13

1.4小结15

第2章 选择排序16

2.1内存的工作原理16

2.2数组和链表18

2.2.1链表19

2.2.2数组20

2.2.3术语21

2.2.4在中间插入22

2.2.5删除23

2.3选择排序25

2.4小结28

第3章 递归29

3.1递归29

3.2基线条件和递归条件32

3.3栈33

3.3.1调用栈34

3.3.2递归调用栈36

3.4小结40

第4章 快速排序41

4.1分而治之41

4.2快速排序47

4.3再谈大O表示法52

4.3.1比较合并排序和快速排序53

4.3.2平均情况和最糟情况54

4.4小结57

第5章 散列表58

5.1散列函数60

5.2应用案例63

5.2.1将散列表用于查找63

5.2.2防止重复64

5.2.3将散列表用作缓存66

5.2.4小结68

5.3冲突69

5.4性能71

5.4.1填装因子72

5.4.2良好的散列函数74

5.5小结75

第6章 广度优先搜索76

6.1图简介77

6.2图是什么79

6.3广度优先搜索79

6.3.1查找最短路径82

6.3.2队列83

6.4实现图84

6.5实现算法86

6.6小结93

第7章 狄克斯特拉算法94

7.1使用狄克斯特拉算法95

7.2术语98

7.3换钢琴100

7.4负权边105

7.5实现108

7.6小结116

第8章 贪婪算法117

8.1教室调度问题117

8.2背包问题119

8.3集合覆盖问题121

8.4NP 问题127

8.4.1旅行商问题详解127

8.4.2如何识别NP 问题131

8.5小结133

第9章 动态规划134

9.1背包问题134

9.1.1简单算法135

9.1.2动态规划136

9.2背包问题FAQ143

9.2.1再增加一件商品将如何呢143

9.2.2行的排列顺序发生变化时结果将如何145

9.2.3可以逐列而不是逐行填充网格吗146

9.2.4增加一件更小的商品将如何呢146

9.2.5可以偷商品的一部分吗146

9.2.6旅游行程化147

9.2.7处理相互依赖的情况148

9.2.8计算最终的解时会涉及两个以上的子背包吗148

9.2.9解可能导致背包没装满吗149

9.3最长公共子串149

9.3.1绘制网格150

9.3.2填充网格151

9.3.3揭晓答案152

9.3.4最长公共子序列153

9.3.5最长公共子序列之解决方案154

9.4小结155

第10章 K 最近邻算法156

10.1橙子还是柚子156

10.2创建推荐系统158

10.2.1特征抽取159

10.2.2回归162

10.2.3挑选合适的特征164

10.3机器学习简介165

10.3.1OCR165

10.3.2创建垃圾邮件过滤器166

10.3.3预测股票市场167

10.4小结167

第11章 接下来如何做168

11.1树168

11.2反向索引171

11.3傅里叶变换171

11.4并行算法172

11.5MapReduce173

11.5.1分布式算法为何很有用173

11.5.2映射函数173

11.5.3归并函数174

11.6布隆过滤器和HyperLogLog174

11.6.1布隆过滤器175

11.6.2HyperLogLog176

11.7SHA 算法176

11.7.1比较文件177

11.7.2检查密码178

11.8局部敏感的散列算法178

11.9Diffie-Hellman 密钥交换179

11.10线性规划180

11.11结语180

练习答案181