声明

本笔记全部内容由Himekawa编写，无AI辅助生成。转载内容请标明出处。

Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.

规范

本笔记需要的所有代码均用C++代码实现。

这是一个长期的项目，预计要一年时间(已经是高中开的坑了)。

本笔记的顺序、内容不会和IA*****保持一致。IA中的思考题部分很可能不会发布。且不保证正确。

本页面的所有笔记均包括以下内容：

  • 正文
  • 数据
  • 代码

*"IA"代指《算法导论》(也可能代指IA?)

目录

第零部分-必需知识

C0.数学知识

  1. 求和
  2. 离散数学
  3. 计数与概率
  4. 矩阵

第一部分-基础知识

C1.算法基础

  1. 排序算法与算法分析
  2. 分治法及其分析

C2.函数的增长

  1. 渐进记号
  2. 标准记号与常用函数

C3.分治策略

  1. 最大子数组问题
  2. 矩阵乘法的Strassen算法
  3. 求解递归式

C4.概率分析及随机算法

  1. 雇用问题
  2. 指示器随机变量
  3. 随机算法
  4. 概率分析的延伸

第二部分-排序算法

C5.堆排序

  1. 堆的使用
  2. 堆排序算法
  3. 优先队列

C6.快速排序

  1. 快速排序的实现与性能分析
  2. 快速排序的随机化版本

C7.线性时间排序

  1. 排序算法的下界
  2. 计数排序
  3. 基数排序
  4. 桶排序

第三部分-数据结构

C8.基本数据结构

  1. 栈和队列
  2. 链表
  3. 指针和对象的实现
  4. 有根树的表示

C9.散列表

  1. 直接寻址表
  2. 散列表

C10.二叉搜索树

  1. 二叉搜索树的查询
  2. 二叉搜索树的插入和删除

C11.红黑树

  1. 红黑树的性质
  2. 红黑树的旋转
  3. 红黑树的插入和删除

C12.数据结构拓展

  1. 动态顺序统计
  2. 区间树

第四部分-高级设计和分析技术

C13.贪心算法

  1. 活动选择问题
  2. 贪心算法原理
  3. 赫夫曼编码
  4. 拟阵

C14.动态规划

  1. 钢条切割
  2. 矩阵链乘法
  3. 动态规划原理
  4. 最长公共子序列
  5. 最优二叉搜索树

C15.摊还分析

  1. 聚合分析
  2. 核算法
  3. 势能法
  4. 动态表

第五部分-高级数据结构

C16.B树

  1. B树的定义
  2. B树的基本操作
  3. 从B树删除关键字

C17.斐波那契堆

  1. 斐波那契堆结构
  2. 可合并堆操作

C18.Van树

  1. Van树的基本方法
  2. Van树的递归结构
  3. Van树的操作

C19.用于不相交集合的数据结构

  1. 不相交集合操作
  2. 不相交集合的链表表示
  3. 不相交集合森林

第六部分-图算法

C20.基本的图算法

  1. 图的表示
  2. 广度优先搜索(DFS)
  3. 深度优先搜索(BFS)
  4. 连通分量

C21.最小生成树

  1. 最小生成树的形成
  2. Kruskal算法

C22.单源最短路径

  1. BF算法
  2. 有向无环图中的单源最短路径
  3. Dijkstra算法

C23.所有节点对的最短路径问题

  1. 最短路径和矩阵乘法
  2. Johnson算法

C24.最大流

  1. 流网络
  2. 最大二分匹配

第七部分-其它算法

C25.矩阵运算

  1. 求解线性方程组
  2. 矩阵求逆
  3. 对称正定矩阵和最小二乘逼近

C26.多项式

  1. 多项式的表示
  2. DFT与FFT

C27.数论算法

  1. 基础数论概念
  2. 最大公约数(gcd)
  3. 模运算
  4. 中国余数定理
  5. RSA公钥加密系统
  6. 素数
  7. 整数的因子分解

C28.字符串算法

  1. 朴素匹配法
  2. 有限自动机
  3. KMP算法

C29.计算几何

  1. 计算集合-线段
  2. 寻找凸包
  3. 寻找最近点对