高级算法和数据结构电子书

内容提要

推荐序

致 谢

前 言

为什么要选择本书

读者对象

本书的内容是如何组织的：路线图

关于代码

作者简介

本书封面简介

第1章 初识数据结构

1.1 数据结构

1.2 设定目标：阅读本书后的期望

1.3 打包背包：数据结构与现实世界的结合

1.4 小结

第一部分 改进基本数据结构

第2章 改进优先队列：d叉堆

2.1 本章结构

2.2 问题：处理优先级

2.3 已知解决方案：让列表保持有序

2.4 描述数据结构API：优先队列

2.5 具体数据结构

2.6 如何实现堆

2.7 用例：找到最大的k个元素

2.8 更多的用例

2.9 对分支因子进行分析[20]

2.10 性能分析：寻找最佳分支因子

2.11 小结

第3章 树堆：使用随机化来平衡二叉搜索树

3.1 问题：多索引

3.2 解决方案：描述与API

3.3 树堆

3.4 应用：随机树堆

3.5 性能分析和剖析

3.6 小结

第4章 布隆过滤器：减少跟踪内容所需的内存

4.1 字典问题：跟踪事物

4.2 实现字典的其他方法

4.3 描述数据结构API：关联数组

4.4 具体数据结构

4.5 表面之下：布隆过滤器是如何工作的

4.6 实现

4.7 应用场景

4.8 为什么布隆过滤器是可行的[13]

4.9 性能分析

4.10 估计布隆过滤器的精确度[17]

4.11 改进的变体

4.12 小结

第5章 不交集：次线性时间的处理过程

5.1 不同子集问题

5.2 解决方案的论证

5.3 描述数据结构API：不交集

5.4 简单解决方案

5.5 使用树状结构[8]

5.6 改进运行时间的启发式算法[10]

5.7 应用程序

5.8 小结

第6章 trie与基数树：高效的字符串搜索

6.1 拼写检查

6.2 trie

6.3 基数树

6.4 应用程序

6.5 小结

第7章 用例：LRU缓存

7.1 不要重复计算

7.2 第一次尝试：记住数据

7.3 内存（真的）不够

7.4 清除陈旧数据：LRU缓存

7.5 当新数据更有价值时：LFU

7.6 如何使用缓存也同样重要

7.7 同步简介

7.8 缓存应用程序

7.9 小结

第二部分 多维查询

第8章 最近邻搜索

8.1 最近邻搜索问题

8.2 解决方案

8.3 描述与API

8.4 迁移到k维空间

8.5 小结

第9章 k-d树：索引多维数据

9.1 从结束的地方继续

9.2 迁移到k维空间：循环遍历维度

9.3 方法

9.4 限制与可能的改进

9.5 小结

第10章 相似性搜索树：图像检索的近似最近邻搜索

10.1 从结束的地方继续

10.2 R树

10.3 SS树

10.4 相似性搜索

10.5 SS+树[16]

10.6 小结

第11章 最近邻搜索的应用

11.1 应用程序：查找最近的枢纽

11.2 中心化应用程序

11.3 迁移到分布式应用程序

11.4 其他应用程序

11.5 小结

第12章 聚类

12.1 聚类简介

12.2 k均值算法

12.3 DBSCAN算法

12.4 OPTICS算法

12.5 评估聚类结果：评估指标

12.6 小结

第13章 并行聚类：MapReduce与树冠聚类

13.1 并行化

13.2 MapReduce

13.3 MapReduce版本的k均值算法

13.4 MapReduce版本的DBSCAN算法

13.5 小结

第三部分 平面图与最小交叉数

第14章 图简介：寻找距离最短的路径

14.1 定义

14.2 图的属性

14.3 图的遍历：BFS与DFS

14.4 加权图中的最短路径：迪杰斯特拉算法

14.5 超越迪杰斯特拉算法：A*算法

14.6 小结

第15章 图嵌入与平面性：绘制具有最少相交边的图

15.1 图嵌入

15.2 平面图

15.3 非平面图

15.4 边的交叉点

15.5 小结

第16章 梯度下降：（不仅是）图的优化问题

16.1 用于交叉数的启发式算法

16.2 优化的工作原理

16.3 梯度下降

16.4 梯度下降的应用

16.5 使用梯度下降进行图嵌入

16.6 小结

第17章 模拟退火：超越局部最小值的优化

17.1 模拟退火

17.2 模拟退火与旅行推销员

17.3 模拟退火与图嵌入

17.4 小结

第18章 遗传算法：受生物学启发的快速收敛优化

18.1 遗传算法简介

18.2 TSP

18.3 最小顶点覆盖

18.4 遗传算法的其他应用

18.5 小结

附录A 伪代码快速指南

A.1 变量与基础知识

A.2 数组

A.3 条件指令

A.4 循环

A.5 代码块与缩进

A.6 函数

附录B 大O符号

B.1 算法与性能

B.2 RAM模型

B.3 数量级

B.4 符号

B.5 示例

附录C 核心数据结构

C.1 核心数据结构

C.2 数组

C.3 链表

C.4 树

C.5 哈希表

C.6 对核心的数据结构进行对比和分析

附录D 类似于优先队列的容器

D.1 背包

D.2 堆栈

D.3 队列

D.4 对不同的容器进行对比和分析

附录E 递归

E.1 简单递归

E.2 尾递归

E.3 互递归

附录F 分类问题与随机算法的度量指标

F.1 决定性问题

F.2 拉斯维加斯算法

F.3 蒙特卡罗算法

F.4 分类问题的度量指标