03《算法导论（第三版）·Thomas H. Cormen等》读书笔记

旧城等待， 2022-04-17 01:22 518阅读 0赞

### 目录 ###

*  第1章 算法在计算中的作用
 *   *  1.1 算法
     *  1.2 作为一种技术的算法
 *  第2章 算法基础
 *   *  2.1 插入排序
     *  2.2 分析算法
     *  2.3 设计算法
     *   *  2.3.1 分治法
         *  2.3.2 分析分治法
 *  第3章 函数的增长
 *   *  3.1 渐近符号
     *  3.2 标准记号与常用函数
 *  第4章 分治算法
 *   *  4.1 最大子数组问题
     *  4.2 矩阵乘法的Strassen算法
     *  4.3 用代入法求解递归式
     *  4.4 用递归树方法求解递归式
     *  4.5 用主方法求解递归式
     *  4.6 证明主定理
     *   *  4.6.1 对b的幂证明主定理
         *  4.6.2 向下取整和向上取整
 *  第5章 概率分析和随机算法
 *   *  5.1 雇用问题
     *  5.2 指示器随机变量
     *  5.3 随机算法
     *  5.4 概率分析和指示器随机变量的进一步使用
     *   *  5.4.1 生日悖论
         *  5.4.2 球与箱子
         *  5.4.3 特征序列
         *  5.4.4 在线雇用问题
 *  第6章 堆排序
 *   *  6.1 堆
     *  6.2 维护堆的性质
     *  6.3 建堆
     *  6.4 堆排序算法
     *  6.5 优先队列
 *  第7章 快速排序
 *   *  7.1 快速排序的描述
     *  7.2 快速排序的性能
     *  7.3 快速排序的随机化版本
     *  7.4 快速排序分析
     *   *  7.4.1 最坏情况分析
         *  7.4.2 期望运行时间
 *  第8章 线性时间排序
 *   *  8.1 排序算法的下界
     *  8.2 计数排序
     *  8.3 基数排序
     *  8.4 桶排序
 *  第9章 中位数和顺序统计量
 *   *  9.1 最小值和最大值
     *  9.2 期望为线性时间的选择算法
     *  9.3 最坏情况为线性时间的选择算法
 *  第10章 基本数据结构
 *   *  10.1 栈和队列
     *  10.2 链表
     *  10.3 指针和对象的实现
     *  10.4 有根树的表示
 *  第11章 散列表
 *   *  11.1 直接寻址表
     *  11.2 散列表
     *  11.3 散列函数
     *   *  11.3.1 除法散列法
         *  11.3.2 乘法散列法
         *  11.3.3 全域散列法
     *  11.4 开放寻址法
     *  11.5 完全散列
 *  第12章 二叉搜索树
 *   *  12.1 什么是二叉搜索树
     *  12.2 查询二叉搜索树
     *  12.3 插入和删除
     *  12.4 随机构建二叉搜索树
 *  第13章 红黑树
 *   *  13.1 红黑树的性质
     *  13.2 旋转
     *  13.3 插入
     *  13.4 删除
 *  第14章 数据结构的额扩张
 *   *  14.1 动态顺序统计
     *  14.2 如何扩张数据结构
     *  14.3 区间树
 *  第15章 动态规划
 *   *  15.1 钢条切割
     *  15.2 矩阵链乘法
     *  15.3 动态规划原理
     *  15.4 最长公共子序列
     *  15.5 最优二叉搜索树
 *  第16章 贪心算法
 *   *  16.1 活动选择问题
     *  16.2 贪心算法原理
     *  16.3 赫夫曼编码
     *  16.4 拟阵和贪心算法
     *  16.5 用拟阵求解任务调度问题
 *  第17章 摊还分析
 *   *  17.1 聚合分析
     *  17.2 核算法
     *  17.3 势能法
     *  17.4 动态表
     *   *  17.4.1 表扩张
         *  17.4.2 表扩张和收缩
 *  第18章 B树
 *   *  18.1 B树的定义
     *  18.2 B树上的基本操作
     *  18.3 从B树中删除关键字
 *  第19章 斐波那契堆
 *   *  19.1 斐波那契堆结构
     *  19.2 可合并堆操作
     *  19.3 关键字减值和删除一个结点
     *  19.4 最大度数的界
 *  第20章 van Emde Boas树
 *   *  20.1 基本方法
     *  20.2 递归结构
     *   *  20.2.1 原型van Emde Boas结构
         *  20.2.2 原型van Emde Boas结构上的操作
     *  20.3 van Emde Boas树及其操作
     *   *  20.3.1 van Emde Boas树
         *  20.3.2 van Emde Boas树的操作
 *  第21章 用于不想交集合的数据
 *   *  21.1 不相交集合的操作
     *  21.2 不相交集合的链表表示
     *  21.3 不相交集合森林
     *  21.4 带路径压缩的按秩合并的分析
 *  第22章 基本的图算法
 *   *  22.1 图的表示
     *  22.2 广度优先搜索
     *  22.3 深度优先搜索
     *  22.4 拓扑排序
     *  22.5 强连通分量
 *  第23章 最小生成树
 *   *  23.1 最小生成树的形成
     *  23.2 Kruskal算法和Prim算法
 *  第24章 单源最短路径
 *   *  24.1 Bellman-Ford算法
     *  24.2 有向无环图中的单源最短路径问题
     *  24.3 Dijkstra算法
     *  24.4 差分约束和最短路径
     *  24.5 最短路径性质的证明
 *  第25章 所有结点对的最短路径
 *   *  25.1 最短路径和矩阵乘法
     *  25.2 Floyd-Warshall算法
     *  25.3 用于稀疏图的Johnson算法
 *  第26章 最大流
 *   *  26.1 流网络
     *  26.2 Ford-Fulkerson方法
     *  26.3 最大二分匹配
     *  26.4 推送-重贴标签算法
     *  26.5 前置重贴标签算法
 *  第27章 多线程算法
 *   *  27.1 动态多线程基础
     *  27.2 多线程矩阵乘法
     *  27.3 多线程归并排序
 *  第28章 矩阵运算
 *   *  28.1 求解线性方程组
     *  28.2 矩阵求逆
     *  28.3 对称正定矩阵和最小二乘逼近
 *  第29章 线性规划
 *   *  29.1 标准型和松弛型
     *  29.2 将问题表达为线性规划
     *  29.3 单纯形算法
     *  29.4 对偶性
     *  29.5 初始基本可行解
 *  第30章多项式与快速傅里叶变换
 *   *  30.1 多项式的表示
     *  30.2 DFT与FFT
     *  30.3 高效FFT实现
 *  第31章 数论算法
 *   *  31.1 基础数论概念
     *  31.2 最大公约数
     *  31.3 模运算
     *  31.4 求解模线性方程
     *  31.5 中国余数定理
     *  31.6 元素的幂
     *  31.7 RSA公钥加密系统
     *  31.8 素数的测试
     *  31.9 整数的因子分解
 *  第32章 字符串匹配
 *   *  32.1 朴素字符串匹配算法
     *  32.2 Rabin-Karp算法
     *  32.3 利用有限自动机进行字符串匹配
     *  32.4 Knuth-Morris-Pratt算法
 *  第33章 计算几何学
 *   *  33.1 线段的性质
     *  33.2 确定任意一对线段是否相交
     *  33.3 寻找凸包
     *  33.4 寻找最近点对
 *  第34章 NP完全性
 *   *  34.1 多项式时间
     *  34.2 多项式时间的验证
     *  34.3 NP完全性与可规约性
     *  34.4 NP完全性的证明
     *  34.5 NP完全问题
     *   *  34.5.1 团问题
         *  34.5.2 顶点覆盖问题
         *  34.5.3 哈密顿回路问题
         *  34.5.4 旅行商问题
         *  34.5.5 子集和问题
 *  第35章 近似算法
 *   *  35.1 顶点覆盖问题
     *  35.2 旅行商问题
     *   *  35.2.1 满足三角不等式的旅行商问题
         *  35.2.2 一般旅行商问题
     *  35.3 集合覆盖问题
     *  35.4 随机化和线性规划
     *  35.5 子集和问题

# 第1章 算法在计算中的作用 #

## 1.1 算法 ##

## 1.2 作为一种技术的算法 ##

# 第2章 算法基础 #

## 2.1 插入排序 ##

## 2.2 分析算法 ##

## 2.3 设计算法 ##

### 2.3.1 分治法 ###

### 2.3.2 分析分治法 ###

# 第3章 函数的增长 #

## 3.1 渐近符号 ##

## 3.2 标准记号与常用函数 ##

# 第4章 分治算法 #

## 4.1 最大子数组问题 ##

## 4.2 矩阵乘法的Strassen算法 ##

## 4.3 用代入法求解递归式 ##

## 4.4 用递归树方法求解递归式 ##

## 4.5 用主方法求解递归式 ##

## 4.6 证明主定理 ##

### 4.6.1 对b的幂证明主定理 ###

### 4.6.2 向下取整和向上取整 ###

# 第5章 概率分析和随机算法 #

## 5.1 雇用问题 ##

## 5.2 指示器随机变量 ##

## 5.3 随机算法 ##

## 5.4 概率分析和指示器随机变量的进一步使用 ##

### 5.4.1 生日悖论 ###

### 5.4.2 球与箱子 ###

### 5.4.3 特征序列 ###

### 5.4.4 在线雇用问题 ###

# 第6章 堆排序 #

## 6.1 堆 ##

## 6.2 维护堆的性质 ##

## 6.3 建堆 ##

## 6.4 堆排序算法 ##

## 6.5 优先队列 ##

# 第7章 快速排序 #

## 7.1 快速排序的描述 ##

## 7.2 快速排序的性能 ##

## 7.3 快速排序的随机化版本 ##

## 7.4 快速排序分析 ##

### 7.4.1 最坏情况分析 ###

### 7.4.2 期望运行时间 ###

# 第8章 线性时间排序 #

## 8.1 排序算法的下界 ##

## 8.2 计数排序 ##

## 8.3 基数排序 ##

## 8.4 桶排序 ##

# 第9章 中位数和顺序统计量 #

## 9.1 最小值和最大值 ##

## 9.2 期望为线性时间的选择算法 ##

## 9.3 最坏情况为线性时间的选择算法 ##

# 第10章 基本数据结构 #

## 10.1 栈和队列 ##

## 10.2 链表 ##

## 10.3 指针和对象的实现 ##

## 10.4 有根树的表示 ##

# 第11章 散列表 #

## 11.1 直接寻址表 ##

## 11.2 散列表 ##

## 11.3 散列函数 ##

### 11.3.1 除法散列法 ###

### 11.3.2 乘法散列法 ###

### 11.3.3 全域散列法 ###

## 11.4 开放寻址法 ##

## 11.5 完全散列 ##

# 第12章 二叉搜索树 #

## 12.1 什么是二叉搜索树 ##

## 12.2 查询二叉搜索树 ##

## 12.3 插入和删除 ##

## 12.4 随机构建二叉搜索树 ##

# 第13章 红黑树 #

## 13.1 红黑树的性质 ##

## 13.2 旋转 ##

## 13.3 插入 ##

## 13.4 删除 ##

# 第14章 数据结构的额扩张 #

## 14.1 动态顺序统计 ##

## 14.2 如何扩张数据结构 ##

## 14.3 区间树 ##

# 第15章 动态规划 #

## 15.1 钢条切割 ##

## 15.2 矩阵链乘法 ##

## 15.3 动态规划原理 ##

## 15.4 最长公共子序列 ##

## 15.5 最优二叉搜索树 ##

# 第16章 贪心算法 #

## 16.1 活动选择问题 ##

## 16.2 贪心算法原理 ##

## 16.3 赫夫曼编码 ##

## 16.4 拟阵和贪心算法 ##

## 16.5 用拟阵求解任务调度问题 ##

# 第17章 摊还分析 #

## 17.1 聚合分析 ##

## 17.2 核算法 ##

## 17.3 势能法 ##

## 17.4 动态表 ##

### 17.4.1 表扩张 ###

### 17.4.2 表扩张和收缩 ###

# 第18章 B树 #

## 18.1 B树的定义 ##

## 18.2 B树上的基本操作 ##

## 18.3 从B树中删除关键字 ##

# 第19章 斐波那契堆 #

## 19.1 斐波那契堆结构 ##

## 19.2 可合并堆操作 ##

## 19.3 关键字减值和删除一个结点 ##

## 19.4 最大度数的界 ##

# 第20章 van Emde Boas树 #

## 20.1 基本方法 ##

## 20.2 递归结构 ##

### 20.2.1 原型van Emde Boas结构 ###

### 20.2.2 原型van Emde Boas结构上的操作 ###

## 20.3 van Emde Boas树及其操作 ##

### 20.3.1 van Emde Boas树 ###

### 20.3.2 van Emde Boas树的操作 ###

# 第21章 用于不想交集合的数据 #

## 21.1 不相交集合的操作 ##

## 21.2 不相交集合的链表表示 ##

## 21.3 不相交集合森林 ##

## 21.4 带路径压缩的按秩合并的分析 ##

# 第22章 基本的图算法 #

## 22.1 图的表示 ##

## 22.2 广度优先搜索 ##

## 22.3 深度优先搜索 ##

## 22.4 拓扑排序 ##

## 22.5 强连通分量 ##

# 第23章 最小生成树 #

## 23.1 最小生成树的形成 ##

## 23.2 Kruskal算法和Prim算法 ##

# 第24章 单源最短路径 #

## 24.1 Bellman-Ford算法 ##

## 24.2 有向无环图中的单源最短路径问题 ##

## 24.3 Dijkstra算法 ##

## 24.4 差分约束和最短路径 ##

## 24.5 最短路径性质的证明 ##

# 第25章 所有结点对的最短路径 #

## 25.1 最短路径和矩阵乘法 ##

## 25.2 Floyd-Warshall算法 ##

## 25.3 用于稀疏图的Johnson算法 ##

# 第26章 最大流 #

## 26.1 流网络 ##

## 26.2 Ford-Fulkerson方法 ##

## 26.3 最大二分匹配 ##

## 26.4 推送-重贴标签算法 ##

## 26.5 前置重贴标签算法 ##

# 第27章 多线程算法 #

## 27.1 动态多线程基础 ##

## 27.2 多线程矩阵乘法 ##

## 27.3 多线程归并排序 ##

# 第28章 矩阵运算 #

## 28.1 求解线性方程组 ##

## 28.2 矩阵求逆 ##

## 28.3 对称正定矩阵和最小二乘逼近 ##

# 第29章 线性规划 #

## 29.1 标准型和松弛型 ##

## 29.2 将问题表达为线性规划 ##

## 29.3 单纯形算法 ##

## 29.4 对偶性 ##

## 29.5 初始基本可行解 ##

# 第30章多项式与快速傅里叶变换 #

## 30.1 多项式的表示 ##

## 30.2 DFT与FFT ##

## 30.3 高效FFT实现 ##

# 第31章 数论算法 #

## 31.1 基础数论概念 ##

## 31.2 最大公约数 ##

## 31.3 模运算 ##

## 31.4 求解模线性方程 ##

## 31.5 中国余数定理 ##

## 31.6 元素的幂 ##

## 31.7 RSA公钥加密系统 ##

## 31.8 素数的测试 ##

## 31.9 整数的因子分解 ##

# 第32章 字符串匹配 #

## 32.1 朴素字符串匹配算法 ##

## 32.2 Rabin-Karp算法 ##

## 32.3 利用有限自动机进行字符串匹配 ##

## 32.4 Knuth-Morris-Pratt算法 ##

# 第33章 计算几何学 #

## 33.1 线段的性质 ##

## 33.2 确定任意一对线段是否相交 ##

## 33.3 寻找凸包 ##

## 33.4 寻找最近点对 ##

# 第34章 NP完全性 #

## 34.1 多项式时间 ##

## 34.2 多项式时间的验证 ##

## 34.3 NP完全性与可规约性 ##

## 34.4 NP完全性的证明 ##

## 34.5 NP完全问题 ##

### 34.5.1 团问题 ###

### 34.5.2 顶点覆盖问题 ###

### 34.5.3 哈密顿回路问题 ###

### 34.5.4 旅行商问题 ###

### 34.5.5 子集和问题 ###

# 第35章 近似算法 #

## 35.1 顶点覆盖问题 ##

## 35.2 旅行商问题 ##

### 35.2.1 满足三角不等式的旅行商问题 ###

### 35.2.2 一般旅行商问题 ###

## 35.3 集合覆盖问题 ##

## 35.4 随机化和线性规划 ##

## 35.5 子集和问题 ##

03《算法导论（第三版）·Thomas H. Cormen等》读书笔记

发表评论取消回复

还没有评论，来说两句吧...

相关阅读

相关算法红皮书第四版读书笔记（三）查找

相关《算法导论》读书笔记（总纲）

相关算法导论-第一部分-读书笔记

相关算法导论-第二部分-读书笔记

相关算法导论-第四部分-读书笔记

相关算法导论-第三部分-读书笔记

相关算法导论-第六部分-读书笔记

相关算法导论-第五部分-读书笔记

相关 03《算法导论（第三版）·Thomas H. Cormen等》读书笔记

相关 04《算法（第四版）·Robert Sedgewick等》读书笔记