算法图解 - 像小说一样有趣的算法入门书

算法图解 - 像小说一样有趣的算法入门书

第1章 算法简介13

1.1 引言13

1.1.1 性能方面13

1.1.2 问题解决技巧14

1.2 二分查找14

1.2.1 更佳的查找方式16

1.2.2 运行时间20

1.3 大O表示法20

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

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

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

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

1.3.5 旅行商25

1.4 小结27

第2章 选择排序28

2.1 内存的工作原理28

2.2 数组和链表30

2.2.1 链表31

2.2.2 数组32

2.2.3 术语33

2.2.4 在中间插入34

2.2.5 删除35

2.3 选择排序37

示例代码40

2.4 小结40

第3章 递归41

3.1 递归41

3.2 基线条件和递归条件44

3.3 栈45

3.3.1 调用栈46

3.3.2 递归调用栈48

3.4 小结52

第4章 快速排序53

4.1 分而治之53

4.2 快速排序59

4.3 再谈大O表示法64

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

4.3.2 平均情况和最糟情况66

4.4 小结69

第5章 散列表70

5.1 散列函数72

5.2 应用案例75

5.2.1 将散列表用于查找75

5.2.2 防止重复76

5.2.3 将散列表用作缓存78

5.2.4 小结80

5.3 冲突81

5.4 性能83

5.4.1 填装因子84

5.4.2 良好的散列函数86

5.5 小结87

第6章 广度优先搜索88

6.1 图简介89

6.2 图是什么91

6.3 广度优先搜索91

6.3.1 查找最短路径94

6.3.2 队列95

6.4 实现图96

6.5 实现算法98

运行时间102

6.6 小结105

第7章 狄克斯特拉算法106

7.1 使用狄克斯特拉算法107

7.2 术语110

7.3 换钢琴112

7.4 负权边117

7.5 实现120

7.6 小结128

第8章 贪婪算法129

8.1 教室调度问题129

8.2 背包问题131

8.3 集合覆盖问题133

近似算法134

8.4 NP完全问题139

8.4.1 旅行商问题详解139

8.4.2 如何识别NP完全问题143

8.5 小结145

第9章 动态规划146

9.1 背包问题146

9.1.1 简单算法147

9.1.2 动态规划148

9.2 背包问题FAQ155

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

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

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

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

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

9.2.6 旅游行程最优化159

9.2.7 处理相互依赖的情况160

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

9.2.9 最优解可能导致背包没装满吗161

9.3 最长公共子串161

9.3.1 绘制网格162

9.3.2 填充网格163

9.3.3 揭晓答案164

9.3.4 最长公共子序列165

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

9.4 小结167

第10章 K最近邻算法168

10.1 橙子还是柚子168

10.2 创建推荐系统170

10.2.1 特征抽取171

10.2.2 回归174

10.2.3 挑选合适的特征176

10.3 机器学习简介177

10.3.1 OCR177

10.3.2 创建垃圾邮件过滤器178

10.3.3 预测股票市场179

10.4 小结179

第11章 接下来如何做180

11.1 树180

11.2 反向索引183

11.3 傅里叶变换183

11.4 并行算法184

11.5 MapReduce185

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

11.5.2 映射函数185

11.5.3 归并函数186

11.6 布隆过滤器和HyperLogLog186

11.6.1 布隆过滤器187

11.6.2 HyperLogLog188

11.7 SHA算法188

11.7.1 比较文件189

11.7.2 检查密码190

11.8 局部敏感的散列算法190

11.9 Diffie-Hellman密钥交换191

11.10 线性规划192

11.11 结语192

练习答案193