内容简介
这是一本关于“高级/进阶”算法和数据结构的图书，主要介绍了用于Web应用程序、系统编程和数据处理领域的各种算法，旨在让读者了解如何用这些算法应对各种棘手的编码挑战，以及如何将其应用于具体问题，以应对新技术浪潮下的“棘手”问题。
本书对一些广为人知的基本算法进行了扩展，还介绍了用于改善优先队列、有效缓存、对数据进行集群等的技术，以期读者能针对不同编程问题选出更好的解决方案。书中示例大多辅以图解，并以不囿于特定语言的伪代码以及多种语言的代码样本加以闸释。
学完本书，读者可以了解高级算法和数据结构的相关内容，并能运用这些知识让代码具备更优性能，甚至能够独立设计数据结构，应对需要自定义解决方案的情况。
本书可作为高等院校计算机相关专业本科高年级学生以及研究生的学习用书，也可供从事与算法相关工作的开发者参考。
展开全文
- 版权信息
- 版 权
- 内容提要
- 推荐序
- 序
- 致谢
- 前言
- 作者简介
- 本书封面简介
- 第1章 初识数据结构
- 1.1 数据结构
- 1.1.1 定义数据结构
- 1.1.2 描述数据结构
- 1.1.3 算法与数据结构有区别吗
- 1.2 设定目标：阅读本书后的期望
- 1.3 打包背包：数据结构与现实世界的结合
- 1.3.1 抽象化问题
- 1.3.2 寻找解决方案
- 1.3.3 拯救大家的算法
- 1.3.4 打破常规来思考问题
- 1.3.5 完美的结局
- 1.4 小结
- 第一部分 改进基本数据结构
- 第2章 改进优先队列：d叉堆
- 2.1 本章结构
- 2.2 问题：处理优先级
- 优先级任务示例：漏洞跟踪
- 2.3 已知解决方案：让列表保持有序
- 从有序列表到优先队列
- 2.4 描述数据结构API：优先队列
- 2.4.1 使用优先队列
- 2.4.2 优先级为何非常重要
- 2.5 具体数据结构
- 2.5.1 性能比较
- 2.5.2 正确的具体数据结构是什么
- 2.5.3 堆
- 2.5.4 优先级、最小堆和最大堆
- 2.5.5 高级变体：d叉堆
- 2.6 如何实现堆
- 2.6.1 向上冒泡
- 2.6.2 向下推动
- 2.6.3 插入
- 2.6.4 移除顶部元素
- 2.6.5 修改
- 2.6.6 处理重复优先级
- 2.6.7 堆化
- 2.6.8 API之外的方法：包含
- 2.6.9 性能回顾
- 2.6.10 从伪代码到实现
- 2.7 用例：找到最大的k个元素
- 2.7.1 选择正确的数据结构
- 2.7.2 正确地使用数据结构
- 2.7.3 代码写起来
- 2.8 更多的用例
- 2.8.1 图中的最小距离：Dijkstra算法
- 2.8.2 更多的图算法：Prim算法
- 2.8.3 数据压缩：霍夫曼编码
- 2.9 对分支因子进行分析[20]
- 2.9.1 是否需要d叉堆
- 2.9.2 运行时间
- 2.9.3 寻找最佳分支因子
- 2.9.4 分支因子与内存的关系
- 2.10 性能分析：寻找最佳分支因子
- 2.10.1 剖析
- 2.10.2 解释结果
- 2.10.3 堆化的谜团
- 2.10.4 选择最佳分支因子
- 2.11 小结
- 第3章 树堆：使用随机化来平衡二叉搜索树
- 3.1 问题：多索引
- 解决方案的要点
- 3.2 解决方案：描述与API
- 3.3 树堆
- 3.3.1 旋转
- 3.3.2 一些设计问题
- 3.3.3 实现搜索方法
- 3.3.4 插入
- 3.3.5 删除
- 3.3.6 去顶、看顶以及修改
- 3.3.7 返回最小键和最大键
- 3.3.8 性能回顾
- 3.4 应用：随机树堆
- 3.4.1 平衡树
- 3.4.2 引入随机化
- 3.4.3 随机树堆的应用
- 3.5 性能分析和剖析
- 3.5.1 理论：期望高度
- 3.5.2 剖析高度
- 3.5.3 剖析运行时间
- 3.5.4 剖析内存使用情况
- 3.5.5 结论
- 3.6 小结
- 第4章 布隆过滤器：减少跟踪内容所需的内存
- 4.1 字典问题：跟踪事物
- 4.2 实现字典的其他方法
- 4.3 描述数据结构API：关联数组
- 4.4 具体数据结构
- 4.4.1 无序数组：快速插入，慢速搜索
- 4.4.2 有序数组和二分查找：慢插入，稍微快一些的搜索
- 4.4.3 哈希表：在不需要有序的情况下，具有平均常数时间的性能
- 4.4.4 二叉搜索树：所有操作都是对数阶的
- 4.4.5 布隆过滤器：与哈希表一样快，但（由于一个缺陷而）更节省内存
- 4.5 表面之下：布隆过滤器是如何工作的
- 4.6 实现
- 4.6.1 使用布隆过滤器
- 4.6.2 位的读取和写入
- 4.6.3 找到键存储的位置
- 4.6.4 生成哈希函数
- 4.6.5 构造函数
- 4.6.6 查找键
- 4.6.7 存储键
- 4.6.8 估计准确率
- 4.7 应用场景
- 4.7.1 缓存
- 4.7.2 路由
- 4.7.3 爬虫
- 4.7.4 I/O提取器
- 4.7.5 拼写检查器
- 4.7.6 分布式数据库和文件系统
- 4.8 为什么布隆过滤器是可行的[13]
- 4.8.1 为什么没有假阴性
- 4.8.2 为什么有假阳性
- 4.8.3 作为随机算法的布隆过滤器
- 4.9 性能分析
- 4.9.1 运行时间
- 4.9.2 构造函数
- 4.9.3 存储元素
- 4.9.4 查找元素
- 4.10 估计布隆过滤器的精确度[17]
- 关于假阳性率公式的说明
- 4.11 改进的变体
- 4.11.1 布隆表过滤器
- 4.11.2 组合布隆过滤器
- 4.11.3 分层布隆过滤器
- 4.11.4 压缩布隆过滤器
- 4.11.5 可扩展布隆过滤器
- 4.12 小结
- 第5章 不交集：次线性时间的处理过程
- 5.1 不同子集问题
- 5.2 解决方案的论证
- 5.3 描述数据结构API：不交集
- 5.4 简单解决方案
- 实现简单解决方案
- 5.5 使用树状结构[8]
- 5.5.1 从链表转移到树
- 5.5.2 实现使用树的版本
- 5.6 改进运行时间的启发式算法[10]
- 5.6.1 路径压缩
- 5.6.2 实现平衡性与路径压缩
- 5.7 应用程序
- 5.7.1 图：连通分量
- 5.7.2 图：最小生成树的Kruskal算法
- 5.7.3 聚类
- 5.7.4 合一
- 5.8 小结
- 第6章 trie与基数树：高效的字符串搜索
- 6.1 拼写检查
- 6.1.1 拼写检查器的设计
- 6.1.2 压缩是关键
- 6.1.3 描述与API
- 6.2 trie
- 6.2.1 为什么trie更好
- 6.2.2 搜索
- 6.2.3 插入
- 6.2.4 删除
- 6.2.5 搜索最长前缀词
- 6.2.6 返回匹配特定前缀的所有键
- 6.2.7 什么时候应该使用trie
- 6.3 基数树
- 6.3.1 节点和边
- 6.3.2 搜索
- 6.3.3 插入
- 6.3.4 删除
- 6.3.5 搜索最长前缀词
- 6.3.6 返回匹配特定前缀的所有键
- 6.4 应用程序
- 6.4.1 拼写检查器
- 6.4.2 字符串相似度
- 6.4.3 字符串排序
- 6.4.4 T9
- 6.4.5 自动完成
- 6.5 小结
- 第7章 用例：LRU缓存
- 7.1 不要重复计算
- 7.2 第一次尝试：记住数据
- 7.2.1 描述与API
- 7.2.2 请保存新数据
- 7.2.3 处理异步调用
- 7.2.4 将缓存的值标记为“正在加载”
- 7.3 内存（真的）不够
- 7.4 清除陈旧数据：LRU缓存
- 7.4.1 有时必须要重复解决问题
- 7.4.2 时间排序
- 7.4.3 性能
- 7.5 当新数据更有价值时：LFU
- 7.5.1 如何选择缓存的清除策略
- 7.5.2 LFU缓存有什么不同
- 7.5.3 性能
- 7.5.4 LFU缓存的不足
- 7.6 如何使用缓存也同样重要
- 7.7 同步简介
- 7.7.1 （在Java中）解决并发问题
- 7.7.2 锁简介
- 7.7.3 获取锁
- 7.7.4 重入锁
- 7.7.5 读锁
- 7.7.6 解决并发的其他方法
- 7.8 缓存应用程序
- 7.9 小结
- 第二部分 多维查询
- 第8章 最近邻搜索
- 8.1 最近邻搜索问题
- 8.2 解决方案
- 8.2.1 第一次尝试
- 8.2.2 有时缓存并不是答案
- 8.2.3 简化事情以获得灵感
- 8.2.4 谨慎选择数据结构
- 8.3 描述与API
- 8.4 迁移到k维空间
- 8.4.1 一维二分查找
- 8.4.2 迁移到更高维度
- 8.4.3 用数据结构对二维空间进行建模
- 8.5 小结
- 第9章 k-d树：索引多维数据
- 9.1 从结束的地方继续
- 9.2 迁移到k维空间：循环遍历维度
- 9.2.1 构造BST
- 9.2.2 不变量
- 9.2.3 保持平衡的重要性
- 9.3 方法
- 9.3.1 搜索
- 9.3.2 插入
- 9.3.3 平衡树
- 9.3.4 删除
- 9.3.5 最近邻搜索
- 9.3.6 区域搜索
- 9.3.7 所有方法的回顾
- 9.4 限制与可能的改进
- 9.5 小结
- 第10章 相似性搜索树：图像检索的近似最近邻搜索
- 10.1 从结束的地方继续
- 10.1.1 一个新的（更复杂的）例子
- 10.1.2 克服k-d树的缺陷
- 10.2 R树
- 10.2.1 先退一步：B树简介
- 10.2.2 由B树到R树
- 10.2.3 在R树中插入点
- 10.2.4 搜索
- 10.3 SS树
- 10.3.1 搜索
- 10.3.2 插入
- 10.3.3 插入：方差、均值与投影
- 10.3.4 插入：分裂节点
- 10.3.5 删除
- 10.4 相似性搜索
- 10.4.1 最近邻搜索
- 10.4.2 区域搜索
- 10.4.3 近似相似性搜索
- 10.5 SS+树[16]
- 10.5.1 SS树会更好吗
- 10.5.2 缓解超球体的限制
- 10.5.3 改进拆分启发式算法
- 10.5.4 减少重叠
- 10.6 小结
- 第11章 最近邻搜索的应用
- 11.1 应用程序：查找最近的枢纽
- 11.1.1 解决方案的初稿
- 11.1.2 天堂里的麻烦
- 11.2 中心化应用程序
- 11.2.1 过滤点
- 11.2.2 复杂的决定
- 11.3 迁移到分布式应用程序
- 11.3.1 处理HTTP通信的问题
- 11.3.2 保持库存同步
- 11.3.3 经验教训
- 11.4 其他应用程序
- 11.4.1 色彩还原
- 11.4.2 粒子的相互作用
- 11.4.3 多维数据库查询的优化
- 11.4.4 聚类
- 11.5 小结
- 第12章 聚类
- 12.1 聚类简介
- 12.1.1 机器学习的类型
- 12.1.2 聚类的类型
- 12.2 k均值算法
- 12.2.1 k均值算法的问题
- 12.2.2 维度诅咒再次来袭
- 12.2.3 k均值算法的性能分析
- 12.2.4 用k-d树来加快k均值算法
- 12.2.5 关于k均值算法的最后一些提示
- 12.3 DBSCAN算法
- 12.3.1 直接可达与密度可达
- 12.3.2 从定义到算法
- 12.3.3 实现
- 12.3.4 DBSCAN算法的优缺点
- 12.4 OPTICS算法
- 12.4.1 定义
- 12.4.2 OPTICS算法的核心思想
- 12.4.3 从可达距离到聚类
- 12.4.4 分层聚类
- 12.4.5 性能分析和最终的考虑
- 12.5 评估聚类结果：评估指标
- 结果解释
- 12.6 小结
- 第13章 并行聚类：MapReduce与树冠聚类
- 13.1 并行化
- 13.1.1 并行计算与分布式计算
- 13.1.2 并行化k均值算法
- 13.1.3 树冠聚类
- 13.1.4 应用树冠聚类
- 13.2 MapReduce
- 13.2.1 MapReduce是如何工作的
- 13.2.2 先映射，后归约
- 13.2.3 表面之下，还有更多
- 13.3 MapReduce版本的k均值算法
- 13.3.1 并行化树冠聚类
- 13.3.2 使用树冠聚类来进行质心的初始化
- 13.3.3 MapReduce版本的树冠聚类
- 13.4 MapReduce版本的DBSCAN算法
- 13.5 小结
- 第三部分 平面图与最小交叉数
- 第14章 图简介：寻找距离最短的路径
- 14.1 定义
- 14.1.1 图的实现
- 14.1.2 作为代数类型的图
- 14.1.3 伪代码
- 14.2 图的属性
- 14.2.1 无向
- 14.2.2 连通
- 14.2.3 无环
- 14.3 图的遍历：BFS与DFS
- 14.3.1 优化配送路线
- 14.3.2 广度优先搜索
- 14.3.3 重建到目标的路径
- 14.3.4 深度优先搜索
- 14.3.5 再次比较队列与堆栈
- 14.3.6 投递包裹的最佳路线
- 14.4 加权图中的最短路径：迪杰斯特拉算法
- 14.4.1 与BFS算法的区别
- 14.4.2 实现
- 14.4.3 分析
- 14.4.4 投递包裹的最佳路线
- 14.5 超越迪杰斯特拉算法：A*算法
- 14.5.1 A*算法到底有多好
- 14.5.2 将启发式函数作为平衡实时数据的一种方式
- 14.6 小结
- 第15章 图嵌入与平面性：绘制具有最少相交边的图
- 15.1 图嵌入
- 15.1.1 一些基础定义
- 15.1.2 完全图与完全二分图
- 15.2 平面图
- 15.2.1 在实践中使用库拉托夫斯基定理
- 15.2.2 平面性测试
- 15.2.3 用于平面性测试的朴素算法
- 15.2.4 提高性能
- 15.2.5 高效的算法
- 15.3 非平面图
- 15.3.1 找到交叉数
- 15.3.2 直线交叉数
- 15.4 边的交叉点
- 15.4.1 直线线段
- 15.4.2 折线
- 15.4.3 贝塞尔曲线
- 15.4.4 二次贝塞尔曲线之间的交点
- 15.4.5 顶点与顶点相交以及边与顶点相交
- 15.5 小结
- 第16章 梯度下降：（不仅是）图的优化问题
- 16.1 用于交叉数的启发式算法
- 16.1.1 刚才提到启发式了吗
- 16.1.2 扩展到曲线边
- 16.2 优化的工作原理
- 16.2.1 成本函数
- 16.2.2 阶跃函数与局部最小值
- 16.2.3 优化随机抽样算法
- 16.3 梯度下降
- 16.3.1 梯度下降中的数学描述
- 16.3.2 几何解释
- 16.3.3 什么时候可以应用梯度下降
- 16.3.4 梯度下降的问题
- 16.4 梯度下降的应用
- 例子：线性回归
- 16.5 使用梯度下降进行图嵌入
- 16.5.1 另一种标准
- 16.5.2 实现
- 16.6 小结
- 第17章 模拟退火：超越局部最小值的优化
- 17.1 模拟退火
- 17.1.1 有时候需要先向上爬才能到达底部
- 17.1.2 实现
- 17.1.3 为什么模拟退火是有效的
- 17.1.4 短程与长程的转换
- 17.1.5 变体
- 17.1.6 模拟退火与梯度下降：应该选择哪一个呢
- 17.2 模拟退火与旅行推销员
- 17.2.1 精确解与近似解
- 17.2.2 可视化成本
- 17.2.3 修剪域
- 17.2.4 状态转换
- 17.2.5 相邻交换与随机交换
- 17.2.6 TSP近似算法的应用
- 17.3 模拟退火与图嵌入
- 17.3.1 最小边交叉
- 17.3.2 力导向绘制
- 17.4 小结
- 第18章 遗传算法：受生物学启发的快速收敛优化
- 18.1 遗传算法简介
- 18.1.1 来自大自然的灵感
- 18.1.2 染色体
- 18.1.3 种群
- 18.1.4 适应度
- 18.1.5 自然选择
- 18.1.6 选择交配的个体
- 18.1.7 交叉操作
- 18.1.8 突变操作
- 18.1.9 遗传算法模板
- 18.1.10 遗传算法在什么时候效果最好
- 18.2 TSP
- 18.2.1 适应度、染色体与初始化
- 18.2.2 突变操作
- 18.2.3 交叉操作
- 18.2.4 结果与参数调整
- 18.2.5 超越TSP：优化整个车队的路线
- 18.3 最小顶点覆盖
- 18.3.1 顶点覆盖的应用
- 18.3.2 实现遗传算法
- 18.4 遗传算法的其他应用
- 18.4.1 最大流问题
- 18.4.2 蛋白质折叠
- 18.4.3 超越遗传算法
- 18.4.4 算法，超越本书
- 18.5 小结
- 附录A 伪代码快速指南
- A.1 变量与基础知识
- A.2 数组
- A.3 条件指令
- A.3.1 else-if语句
- A.3.2 switch语句
- A.4 循环
- A.4.1 for循环
- A.4.2 while循环
- A.4.3 break语句与continue语句
- A.5 代码块与缩进
- A.6 函数
- A.6.1 重载与默认参数
- A.6.2 元组
- A.6.3 元组与解构对象
- 附录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.5.1 存储键-值对
- C.5.2 哈希
- C.5.3 哈希的碰撞解决方法
- C.5.4 性能
- C.6 对核心的数据结构进行对比和分析
- 附录D 类似于优先队列的容器
- D.1 背包
- D.2 堆栈
- D.3 队列
- D.4 对不同的容器进行对比和分析
- 附录E 递归
- E.1 简单递归
- E.1.1 陷阱
- E.1.2 好的递归
- E.2 尾递归
- E.3 互递归
- 附录F 分类问题与随机算法的度量指标
- F.1 决定性问题
- F.2 拉斯维加斯算法
- F.3 蒙特卡罗算法
- F.4 分类问题的度量指标
- F.4.1 准确率
- F.4.2 精确度与召回率
- F.4.3 其他度量指标与回顾
展开全部
版权信息
出版社：人民邮电出版社
出版时间：2023
作者：LA
温馨提示：
1.本电子书已获得正版授权，由出版社通过知传链发行。
2.该电子书为虚拟物品，付费之后概不接收任何理由退款。电子书内容仅支持在线阅读，不支持下载。
3.您在本站购买的阅读使用权仅限于您本人阅读使用，您不得/不能给任何第三方使用，由此造成的一切相关后果本平台保留向您追偿索赔的权利！版权所有，后果自负！
得书感谢您对《高级算法和数据结构》关注和支持，如本书内容有不良信息或侵权等情形的，请联系本网站。
出版时间：2023
作者：LA
温馨提示：
1.本电子书已获得正版授权，由出版社通过知传链发行。
2.该电子书为虚拟物品，付费之后概不接收任何理由退款。电子书内容仅支持在线阅读，不支持下载。
3.您在本站购买的阅读使用权仅限于您本人阅读使用，您不得/不能给任何第三方使用，由此造成的一切相关后果本平台保留向您追偿索赔的权利！版权所有，后果自负！
得书感谢您对《高级算法和数据结构》关注和支持，如本书内容有不良信息或侵权等情形的，请联系本网站。
高级算法和数据结构
免费读 (VIP)