豆瓣高分 类型
9.0 豆瓣评分
可以朗读 语音朗读
109千字 字数
2019-01-01 发行日期
展开全部

主编推荐语

算法详解系列1：基础算法、渐进分析、分冶法、随机化、排序/选择。

内容简介

算法详解系列图书共有4卷，本书是第一卷——基础算法。本书共有6章，主要介绍了4个主题，它们分别是渐进性分析和大O表示法、分冶算法和主方法、随机化算法以及排序和选择。附录A和附录B简单介绍了数据归纳法和离散概率的相关知识。本书的每一章均有小测验、章末习题和编程题，这为读者的自我检查以及进一步学习提供了较多的便利。

目录

  • 版权信息
  • 内容提要
  • 前言
  • 资源与支持
  • 第1章 绪论
  • 1.1 为什么要学习算法
  • 1.2 整数乘法
  • 1.2.1 问题和解决方案
  • 1.2.2 整数乘法问题
  • 1.2.3 小学算法
  • 1.2.4 操作数量的分析
  • 1.2.5 还能做得更好吗
  • 1.3 Karatsuba乘法
  • 1.3.1 一个具体的例子
  • 1.3.2 一种递归算法
  • 1.3.3 Karatsuba乘法
  • 1.4 MergeSort算法
  • 1.4.1 推动力
  • 1.4.2 排序
  • 1.4.3 一个例子
  • 1.4.4 伪码
  • 1.4.5 Merge子程序
  • 1.5 MergeSort算法分析
  • 1.5.1 Merge的运行时间
  • 1.5.2 MergeSort的运行时间
  • 1.5.3 定理1.2的证明
  • 1.5.4 小测验1.1～1.2的答案
  • 1.6 算法分析的指导原则
  • 1.6.1 第1个原则：最坏情况分析
  • 1.6.2 第2个原则：全局分析
  • 1.6.3 第3个原则：渐进性分析
  • 1.6.4 什么是“快速”算法
  • 1.7 本章要点
  • 1.8 习题
  • 挑战题
  • 编程题
  • 第2章 渐进性表示法
  • 2.1 要旨
  • 2.1.1 推动力
  • 2.1.2 高级思维
  • 2.1.3 4个例子
  • 2.1.4 小测验2.1～2.4的答案
  • 2.2 大O表示法
  • 2.2.1 文本定义
  • 2.2.2 图形定义
  • 2.2.3 数学定义
  • 2.3 两个基本例子
  • 2.3.1 k阶多项式是O(nk)
  • 2.3.2 k阶多项式不是O(nk−1)
  • 2.4 大Ω和大Θ表示法
  • 2.4.1 大Ω表示法
  • 2.4.2 大Θ表示法
  • 2.4.3 小O表示法
  • 2.4.4 渐进性表示法的来源
  • 2.4.5 小测验2.5的答案
  • 2.5 其他例子
  • 2.5.1 在指数中添加一个常数
  • 2.5.2 指数乘以一个常数
  • 2.5.3 最大值vs.和
  • 2.6 本章要点
  • 2.7 习题
  • 第3章 分治算法
  • 3.1 分治法规范
  • 3.2 以O(n log n)时间计数逆序对
  • 3.2.1 问题
  • 3.2.2 一个例子
  • 3.2.3 协同筛选
  • 3.2.4 穷举搜索法
  • 3.2.5 分治法
  • 3.2.6 高级算法
  • 3.2.7 关键思路：站在MergeSort的肩膀上
  • 3.2.8 重温Merge
  • 3.2.9 Merge和分离逆序对
  • 3.2.10 Merge_and_CountSplitInv
  • 3.2.11 正确性
  • 3.2.12 运行时间
  • 3.2.13 小测验3.1～3.2的答案
  • 3.3 Strassen的矩阵相乘算法
  • 3.3.1 矩阵相乘
  • 3.3.2 例子（n = 2）
  • 3.3.3 简单算法
  • 3.3.4 分治法
  • 3.3.5 节省一个递归调用
  • 3.3.6 细节
  • 3.3.7 小测验3.3的答案
  • *3.4 O(n log n)时间的最近点对（Closest Pair）算法
  • 3.4.1 问题
  • 3.4.2 热身：1D情况
  • 3.4.3 预处理
  • 3.4.4 一种分治方法
  • 3.4.5 一个微妙的变化
  • 3.4.6 ClosestSplitPair
  • 3.4.7 正确性
  • 3.4.8 辅助结论3.3（a）的证明
  • 3.4.9 辅助结论3.3（b）的证明
  • 3.4.10 小测验3.4的答案
  • 3.5 本章要点
  • 3.6 习题
  • 挑战题
  • 编程题
  • 第4章 主方法
  • 4.1 重温整数乘法
  • 4.1.1 RecIntMult算法
  • 4.1.2 Karatsuba算法
  • 4.1.3 比较递归过程
  • 4.2 形式声明
  • 4.2.1 标准递归过程
  • 4.2.2 主方法的陈述和讨论
  • 4.3 6个例子
  • 4.3.1 重温MergeSort
  • 4.3.2 二分搜索
  • 4.3.3 整数乘法的递归算法
  • 4.3.4 Karatsuba乘法
  • 4.3.5 矩阵乘法
  • 4.3.6 一个虚构的递归过程
  • 4.3.7 小测验4.2～4.3的答案
  • *4.4 主方法的证明
  • 4.4.1 前言
  • 4.4.2 重温递归树
  • 4.4.3 单层所完成的工作
  • 4.4.4 各层累计
  • 4.4.5 正义与邪恶：需要考虑3种情况
  • 4.4.6 预告运行时间上界
  • 4.4.7 最后的计算：第一种情况
  • 4.4.8 迂回之旅：几何级数
  • 4.4.9 最后的计算：第二种情况和第三种情况
  • 4.4.10 小测验4.4～4.5的答案
  • 4.5 本章要点
  • 4.6 习题
  • 挑战题
  • 第5章 快速排序（QuickSort）
  • 5.1 概述
  • 5.1.1 排序
  • 5.1.2 根据基准元素进行划分
  • 5.1.3 高级描述
  • 5.1.4 内容前瞻
  • 5.2 围绕基准元素进行划分
  • 5.2.1 简易方法
  • 5.2.2 原地实现：高级计划
  • 5.2.3 例子
  • 5.2.4 Partition子程序的伪码
  • 5.2.5 QuickSort的伪码
  • 5.3 良好的基准元素的重要性
  • 5.3.1 ChoosePivot的简单实现
  • 5.3.2 ChoosePivot的过度实现
  • 5.3.3 小测验5.1～5.2的答案
  • 5.4 随机化的QuickSort
  • 5.4.1 ChoosePivot的随机化实现
  • 5.4.2 随机化QuickSort的运行时间
  • 5.4.3 直觉：随机基准元素为什么很好
  • *5.5 随机化QuickSort的分析
  • 5.5.1 预备工作
  • 5.5.2 分解蓝图
  • 5.5.3 应用蓝图
  • 5.5.4 计算比较的概率
  • 5.5.5 最后的计算
  • 5.5.6 小测验5.3的答案
  • *5.6 排序需要Ω (n log n)的比较
  • 5.6.1 基于比较的排序算法
  • 5.6.2 具有更强前提的更快速排序
  • 5.6.3 定理5.5的证明
  • 5.7 本章要点
  • 5.8 习题
  • 挑战题
  • 编程题
  • 第6章 线性时间级的选择
  • 6.1 RSelect算法
  • 6.1.1 选择问题
  • 6.1.2 简化为排序
  • 6.1.3 分治法
  • 6.1.4 RSelect的伪码
  • 6.1.5 RSelect的运行时间
  • 6.1.6 小测验6.1～6.2的答案
  • *6.2 RSelect的分析
  • 6.2.1 根据阶段追踪进展
  • 6.2.2 简化为掷硬币
  • 6.2.3 综合结论
  • *6.3 DSelect算法
  • 6.3.1 基本思路：中位的中位元素
  • 6.3.2 DSelect的伪码
  • 6.3.3 理解DSelect
  • 6.3.4 DSelect的运行时间
  • *6.4 DSelect的分析
  • 6.4.1 递归调用之外所完成的工作
  • 6.4.2 一个粗略的递归过程
  • 6.4.3 30-70辅助结论
  • 6.4.4 解析递归过程
  • 6.4.5 先猜后验方法
  • 6.5 本章要点
  • 6.6 本章习题
  • 挑战题
  • 编程题
  • 附录A 快速回顾数学归纳法
  • A.1 数学归纳法的模板
  • A.2 实例：闭合公式
  • A.3 实例：完全二叉树的大小
  • 附录B 快速回顾离散概率
  • B.1 取样空间
  • B.2 事件
  • B.2.1 小测验B.1的答案
  • B.2.2 小测验B.2的答案
  • B.3 随机变量
  • B.4 期望值
  • B.4.1 小测验B.3的答案
  • B.4.2 小测验B.4的答案
  • B.5 线性期望值
  • B.5.1 形式声明和用例
  • B.5.2 证明
  • B.6 实例：负载平衡
展开全部

评分及书评

评分不足
1个评分

出版方

人民邮电出版社

人民邮电出版社是工业和信息化部主管的大型专业出版社，成立于1953年10月1日。人民邮电出版社坚持“立足信息产业、面向现代社会、传播科学知识、服务科教兴国”，致力于通信、计算机、电子技术、教材、少儿、经管、摄影、集邮、旅游、心理学等领域的专业图书出版。