算法图解

第1章　算法简介1

1.1　引言1

1.1.1　性能方面1

1.1.2　问题解决技巧2

1.2　二分查找2

1.2.1　更佳...

第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.4　NP 完全问题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.1　OCR165

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.5　MapReduce173

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

11.5.2　映射函数173

11.5.3　归并函数174

11.6　布隆过滤器和HyperLogLog174

11.6.1　布隆过滤器175

11.6.2　HyperLogLog176

11.7　SHA算法176

11.7.1　比较文件177

11.7.2　检查密码178

11.8　局部敏感的散列算法178

11.9　Diffie-Hellman密钥交换179

11.10　线性规划180

11.11　结语180

练习答案 181

...

(查看全部试读)