编辑推荐
算法详解系列1：基础算法、渐进分析、分冶法、随机化、排序/选择。
内容简介
算法是计算机科学领域重要的基石之一。算法是程序的灵魂，只有掌握了算法，才能轻松地驾驭程序开发。
算法详解系列图书共有4卷，本书是第1卷——算法基础。本书共有6章，主要介绍了4个主题，它们分别是渐进性分析和大O表示法、分治算法和主方法、随机化算法以及排序和选择。附录A和附录B简单介绍了数据归纳法和离散概率的相关知识。本书的每一章均有小测验、章末习题和编程题，这为读者的自我检查以及进一步学习提供了较多的便利。
本书为对算法感兴趣的广大读者提供了丰富而实用的资料，能够帮助读者提升算法思维能力。本书适合计算机专业的高校教师和学生，想要培养和训练算法思维和计算思维的IT专业人士，以及在准备面试的应聘者和面试官阅读参考。
作者简介
蒂姆·拉夫加登（Tim Roughgarden）是斯坦福大学计算机科学系的教授,也是该校管理科学和工程系的客座教授，他从2004年开始教授和研究算法。本书是他的《算法详解》四部曲的第一卷，基于他从2012年开始定期举行的在线算法课程编写。
章节目录
版权信息
内容提要
前言
资源与支持
第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）：算法基础是2019年由人民邮电出版社出版,作者。
得书感谢您对《算法详解（卷1）：算法基础》关注和支持，如本书内容有不良信息或侵权等情形的，请联系本网站。
