《算法导论》(Introduction to Algorithm) - 笔记目录
声明
笔记很可能会有不足之处，欢迎在评论区指出。
本笔记全部内容由Himekawa编写，转载请标明出处。
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.
规范
本笔记预计为29~30章。文章篇数约80~110篇。
本笔记所有代码为C++代码。
这是一个长期的项目，预计要2~4年。
本笔记的顺序、内容不会和IA*保持一致。
IA中的”思考题“部分很可能不会按顺序发布，甚至不发布。且不保证正确。
本页面的所有笔记均包括以下内容：
正文
数据
代码
*"IA"代指《算法导论》。(也可能代指IA)
目录
第零部分-必需知识
C0.数学知识
求和
基础离散数学
计数与概率
矩阵
第一部分-基础知识
C1.算法基础
插入排序
分析算法
分治法及其分析
C2.函数的增长
渐进记号
标准记号与常用函数
C3.分治策略
最大子数组问题
矩阵乘法的Strassen算法
求解递归式
C4.概率分析及随机算法
雇用问题
指示器随机变量
随机算法
概率分析的延伸
第二部分-排序算法
C5.堆排序
堆的使用
堆排序算法
优先队列
C6.快速排序
快速排序的实现与性能分析
快速排序的随机化版本
C7.线性时间排序
排序算法的下界
计数排序
基数排序
桶排序
第三部分-数据结构
C8.基本数据结构
栈和队列
链表
指针和对象的实现
有根树的表示
C9.散列表
直接寻址表
散列表
C10.二叉搜索树
二叉搜索树的查询
二叉搜索树的插入和删除
C11.红黑树
红黑树的性质
红黑树的旋转
红黑树的插入和删除
C12.数据结构拓展
动态顺序统计
区间树
第四部分-高级设计和分析技术
C13.贪心算法
活动选择问题
贪心算法原理
赫夫曼编码
拟阵
C14.动态规划
钢条切割
矩阵链乘法
动态规划原理
最长公共子序列
最优二叉搜索树
C15.摊还分析
聚合分析
核算法
势能法
动态表
第五部分-高级数据结构
C16.B树
B树的定义
B树的基本操作
从B树删除关键字
C17.斐波那契堆
斐波那契堆结构
可合并堆操作
C18.Van树
Van树的基本方法
Van树的递归结构
Van树的操作
C19.用于不相交集合的数据结构
不相交集合操作
不相交集合的链表表示
不相交集合森林
第六部分-图算法
C20.基本的图算法
图的表示
广度优先搜索(DFS)
深度优先搜索(BFS)
强连通分量
C21.最小生成树
最小生成树的形成
Kruskal算法
C22.单源最短路径
BF算法
有向无环图中的单源最短路径
Dijkstra算法
C23.所有节点对的最短路径问题
最短路径和矩阵乘法
Johnson算法
C24.最大流
流网络
最大二分匹配
第七部分-其它算法
C25.矩阵运算
求解线性方程组
矩阵求逆
对称正定矩阵和最小二乘逼近
C26.多项式
多项式的表示
DFT与FFT
C27.数论算法
基础数论概念
最大公约数(gcd)
模运算
中国余数定理
RSA公钥加密系统
素数
整数的因子分解
C28.字符串算法
朴素匹配法
有限自动机
KMP算法
C29.计算几何
计算集合-线段
寻找凸包
寻找最近点对