算法查找目录

1. 基础数据结构

• 数组与链表
  • 动态数组
    • 实现与自动扩容机制
    • 均摊分析
    • ArrayList/Vector实现
  • 单向链表
    • 基本操作(插入、删除、查找)
    • 链表反转
    • 环检测(Floyd判圈算法)
  • 双向链表
    • 插入删除操作优化
    • 双向遍历优势
    • 边界情况处理
  • 循环链表
    • 约瑟夫环问题
    • 单向循环链表
    • 双向循环链表
  • 跳表
    • 基本原理与实现
    • 概率分析
    • 与平衡树的对比
• 栈与队列
  • 栈的实现与应用
    • 数组实现栈
    • 链表实现栈
    • 表达式求值
    • 括号匹配
    • 函数调用栈模拟
  • 队列的实现与应用
    • 数组实现队列
    • 链表实现队列
    • 循环队列
    • 广度优先搜索应用
  • 双端队列
    • 双端队列实现技巧
    • 应用场景
    • 滑动窗口算法
  • 优先队列
    • 基于堆的实现
    • 基于有序数组的实现
    • 事件调度应用
• 树结构
  • 二叉树
    • 树的遍历(前序、中序、后序、层序)
    • 递归与迭代实现
    • Morris遍历
    • 二叉树序列化与反序列化
  • 二叉搜索树
    • 插入、查找、删除操作
    • 高度分析
    • 中序遍历的有序性
    • 二叉搜索树重构
  • AVL树
    • 平衡因子
    • 左旋与右旋
    • 插入和删除的再平衡
    • 与红黑树的对比
  • 红黑树
    • 五条性质
    • 插入操作与调整
    • 删除操作与调整
    • 应用案例
  • B树/B+树
    • B树的定义与性质
    • B+树的改进
    • 插入与分裂
    • 删除与合并
    • 数据库索引应用
  • 线段树
    • 构建线段树
    • 区间查询
    • 区间更新
    • 懒惰传播
    • 区间最值、区间和应用
  • 树状数组(Binary Indexed Tree/Fenwick Tree)
    • 原理与实现
    • 单点更新与区间查询
    • 区间更新实现
    • 二维树状数组
  • Trie树(前缀树)
    • 字典实现
    • 字符串检索
    • 前缀统计
    • 压缩前缀树
  • 后缀树
    • 构建方法
    • 字符串匹配应用
    • 与后缀数组关系
  • 区间树(Interval Tree)
    • 区间重叠查询
    • 与线段树的区别
  • 四叉树/八叉树
    • 空间划分
    • 图像处理应用
  • 自平衡二叉搜索树变种
    • 伸展树(Splay Tree)
    • 替罪羊树(Scapegoat Tree)
    • 树堆(Treap)
• 堆
  • 二叉堆
    • 最大堆/最小堆
    • 堆化(Heapify)
    • 上浮与下沉操作
    • 堆排序
  • 斐波那契堆
    • 可合并堆操作
    • 渐进复杂度分析
    • 与二叉堆对比
  • 左偏堆
    • 可合并堆实现
    • 左偏性质维护
  • 配对堆
    • 基本操作
    • 复杂度分析
  • d-堆
    • 多叉堆实现
    • 应用场景
• 哈希表
  • 哈希函数
    • 除法哈希法
    • 乘法哈希法
    • 全域哈希
    • 密码学哈希函数
  • 冲突解决
    • 开放寻址法
      • 线性探测
      • 二次探测
      • 双重哈希
    • 链地址法
      • 简单链表
      • 平衡树
    • Robin Hood哈希
    • 布谷鸟哈希
  • 动态扩容与缩容
    • 负载因子
    • 渐进式重哈希
  • 完美哈希
    • 静态数据集优化
  • 一致性哈希
    • 哈希环
    • 虚拟节点
    • 分布式缓存应用
  • 布隆过滤器
    • 空间效率
    • 误判率分析
    • 计数布隆过滤器
• 图
  • 图的表示
    • 邻接矩阵
      • 稠密图优势
      • 空间复杂度
    • 邻接表
      • 稀疏图优势
      • 出边快速访问
    • 十字链表
      • 有向图优化
      • 入边出边同等访问
    • 多重邻接表
      • 无向图优化
      • 边的快速删除
    • 边集数组
      • 简单实现
      • Kruskal算法应用
  • 特殊图结构
    • 星形图
    • 网格图
    • 完全图
    • 二部图
    • DAG(有向无环图)
• 缓存结构与替换策略
  • 基本缓存策略
    • LRU (最近最少使用)
      • 双向链表+哈希表实现
      • O(1)时间复杂度操作
    • LFU (最不经常使用)
      • 频率统计实现
      • O(1)时间复杂度优化
    • FIFO (先进先出)
      • 队列实现
      • 简单性与局限性
    • Clock算法
      • 二次机会法
      • 循环链表实现
  • 高级缓存策略
    • ARC (自适应替换缓存)
      • LRU与LFU的结合
      • 自适应调整
    • W-TinyLFU
      • 窗口TinyLFU
      • 频率估计器
      • 布隆过滤器应用
    • 2Q缓存
      • 多级队列设计
      • 冷热数据分离
    • LIRS (低访问频率驱逐)
      • 重用距离概念
      • 实现细节
    • CLOCK-Pro
      • Clock改进版
      • 冷热数据识别
  • 分布式缓存
    • 一致性哈希在缓存中的应用
    • 缓存同步策略
    • 缓存穿透/击穿/雪崩解决方案
  • 多级缓存体系
    • 层次化缓存设计
    • CPU缓存、内存、磁盘层次

2. 搜索算法

• 基本搜索
  • 线性搜索
    • 无序数据搜索
    • 最坏时间复杂度
    • 平均时间复杂度
  • 二分搜索
    • 有序数据前提
    • 迭代与递归实现
    • 边界条件处理
    • 变种(查找第一个/最后一个等于给定值)
  • 插值搜索
    • 均匀分布数据优化
    • 时间复杂度分析
  • 跳跃搜索
    • 分块搜索
    • 最优块大小
  • 斐波那契搜索
    • 黄金分割思想
    • 与二分查找对比
  • 指数搜索
    • 无界数组搜索
    • 时间复杂度分析
• 树搜索算法
  • 深度优先搜索(DFS)
    • 递归实现
    • 迭代实现(栈)
    • 回溯与剪枝
    • 空间复杂度分析
  • 广度优先搜索(BFS)
    • 队列实现
    • 层次遍历
    • 最短路径应用
    • 空间复杂度分析
  • 双向搜索
    • 从起点和终点同时搜索
    • 空间优化
    • 应用场景
  • 启发式搜索
    • 最佳优先搜索
    • 贪婪最佳优先搜索
  • A*搜索
    • 启发函数设计
    • 曼哈顿/欧几里得距离
    • 完备性与最优性证明
    • 改进版本(IDA*, SMA*)
  • Alpha-Beta剪枝
    • 极小极大算法优化
    • 博弈树搜索
    • 剪枝效率分析
  • 蒙特卡洛树搜索
    • 四个阶段(选择、扩展、模拟、回传)
    • UCB(上置信界)算法
    • 围棋AI应用
  • 迭代深化搜索
    • 深度限制DFS
    • 空间优化
    • IDDFS(迭代加深DFS)
  • 模式搜索
    • Bloom过滤器应用
    • 近似字符串匹配
• 图搜索算法的应用
  • 迷宫求解
  • 八数码/十五数码问题
  • 扫雷游戏AI
  • 棋类游戏搜索

3. 排序算法

• 基本排序
  • 冒泡排序
    • 基本实现
    • 优化(提前终止)
    • 稳定性分析
  • 选择排序
    • 基本实现
    • 不稳定性分析
    • 空间复杂度优势
  • 插入排序
    • 基本实现
    • 对小数据量/近乎有序数据的高效性
    • 稳定性分析
    • 二分插入排序优化
  • 希尔排序
    • 增量序列选择
    • 与插入排序关系
    • 不稳定性分析
• 高效排序
  • 归并排序
    • 分治思想
    • 递归实现
    • 迭代实现
    • 原地归并优化
    • 稳定性分析
  • 快速排序
    • 基本实现
    • 主元选择优化(三数取中法)
    • 尾递归优化
    • 三路快排
    • 不稳定性分析
  • 堆排序
    • 构建堆过程
    • 时间复杂度分析
    • 不稳定性分析
    • 原地排序特性
  • 计数排序
    • 适用条件
    • 稳定性实现
    • 空间复杂度分析
  • 桶排序
    • 桶的数量选择
    • 桶内排序算法
    • 均匀分布效率分析
  • 基数排序
    • LSD与MSD方法
    • 适用数据类型
    • 时间复杂度分析
• 特殊排序
  • 外部排序
    • 多路归并
    • 败者树
    • 置换-选择算法
    • 多阶段合并
  • TimSort
    • 自然排序段识别
    • minrun选择
    • galloping模式
    • 归并优化
  • 内省排序(IntroSort)
    • 快排、堆排、插入排序结合
    • 深度限制机制
    • 实际应用(C++标准库)
  • 拓扑排序
    • 基于DFS实现
    • 基于入度的实现(Kahn算法)
    • 环检测
    • 多解问题
  • 偏序关系排序
  • 混合排序策略
    • Timsort原理
    • 适应性排序算法设计
• 排序算法分析与比较
  • 时间复杂度对比
  • 空间复杂度对比
  • 稳定性对比
  • 适用场景分析
  • 缓存友好性分析

4. 图论算法

• 图的表示与基础操作
  • 邻接矩阵表示
  • 邻接表表示
  • 十字链表表示
  • 图的遍历
    • 深度优先遍历
    • 广度优先遍历
• 最短路径
  • 单源最短路径
    • Dijkstra算法
      • 朴素实现
      • 优先队列优化
      • 适用条件(无负权)
    • Bellman-Ford算法
      • 基本实现
      • 队列优化(SPFA)
      • 负环检测
    • 0-1 BFS(双端队列BFS)
      • 权值为0或1的图
      • 时间复杂度优势
  • 全源最短路径
    • Floyd-Warshall算法
      • 动态规划思想
      • 路径重建
      • 时空复杂度分析
    • Johnson算法
      • 结合Bellman-Ford与Dijkstra
      • 适用于稀疏图
      • 复杂度分析
    • A*算法
      • 启发函数设计
      • 完备性与最优性
      • 应用场景
• 最小生成树
  • Prim算法
    • 朴素实现
    • 优先队列优化
    • 适用于稠密图
  • Kruskal算法
    • 并查集实现
    • 适用于稀疏图
  • Borůvka算法
    • 并行实现潜力
    • 历史意义
  • 次小生成树
  • 度限制生成树
• 网络流
  • 基本概念
    • 流网络
    • 残存网络
    • 割
  • 最大流
    • Ford-Fulkerson算法
      • 增广路径方法
      • 收敛条件
    • Edmonds-Karp算法
      • BFS寻找增广路
      • 复杂度改进
    • Dinic算法
      • 层次图概念
      • 多路增广
      • 复杂度分析
    • 推送-重标记算法
      • 基本操作
      • 全局重标记优化
      • FIFO实现
    • MPM算法
  • 最小费用最大流
    • 费用流概念
    • 消圈算法
    • 结合最短路的SSP算法
  • 应用
    • 二分图最大匹配
    • 项目选择问题
    • 最大密度子图
• 匹配
  • 二分图匹配
    • 匈牙利算法
      • 交替路实现
      • DFS与BFS版本
    • Hopcroft-Karp算法
      • 多路增广
      • 复杂度优势
  • 一般图匹配
    • 带花树算法(Blossom Algorithm)
    • 带权匹配
  • 稳定婚姻问题
    • Gale-Shapley算法
    • 最优性与公平性
    • 应用(医院分配问题)
  • 最大权二分匹配
    • KM算法(Kuhn-Munkres)
    • 匈牙利算法扩展
• 强连通分量
  • Kosaraju算法
    • 两次DFS技巧
    • 时间复杂度分析
  • Tarjan算法
    • 单次DFS实现
    • 低连接值概念
    • 栈应用
  • Gabow算法
  • 强连通分量应用
    • 缩点
    • 2-SAT问题
• 割点与桥
  • Tarjan算法识别割点
  • Tarjan算法识别割边(桥)
  • 双连通分量
  • 边双连通分量
• 二分图
  • 二分图判定
  • 二分图最大匹配
  • 二分图最大权匹配
  • 二分图最小点覆盖
  • 二分图最大独立集
  • König定理
• 其他图算法
  • 欧拉路径/回路
    • Fleury算法
    • Hierholzer算法
    • 应用(一笔画问题)
  • 哈密顿路径/回路
    • 回溯算法
    • 动态规划方法
    • NP完全性
  • 图着色算法
    • 贪心着色
    • 回溯着色
    • Welsh-Powell算法
    • 应用(寄存器分配)
  • 最大团算法
    • Bron–Kerbosch算法
    • 剪枝技术
  • 平面图算法
    • 平面性测试
    • 面提取
  • 支配树
    • Lengauer-Tarjan算法
    • 编译器优化应用
  • 最小树形图(最小树形图)
    • Chu–Liu/Edmonds算法
    • 有向图生成树
  • 斯坦纳树问题
    • 近似算法
    • 精确算法

5. 字符串算法

• 模式匹配
  • 朴素字符串匹配
    • 暴力匹配
    • 时间复杂度分析
  • KMP算法
    • 部分匹配表(next数组)
    • 失配函数构造
    • 复杂度分析
  • Boyer-Moore算法
    • 坏字符规则
    • 好后缀规则
    • 实际效率分析
  • Rabin-Karp算法
    • 哈希函数设计
    • 滚动哈希技术
    • 多模式扩展
  • Aho-Corasick算法
    • AC自动机构建
    • 失配指针
    • 多模式匹配优势
  • Sunday算法
    • 快速跳转
    • 实际效率
  • Shift-And/Shift-Or算法
    • 位并行技术
    • 近似字符串匹配扩展
• 字符串距离
  • 编辑距离
    • 莱文斯坦距离
      • 动态规划实现
      • 空间优化
    • 汉明距离
      • 位运算优化
      • 应用场景
    • Damerau-Levenshtein距离
      • 换位操作
    • 最长公共子序列
      • 动态规划方法
      • 空间优化
      • 多序列扩展
    • 最长公共子串
      • 后缀数组解法
      • 动态规划解法
  • 相似度度量
    • Jaccard相似系数
    • 余弦相似度
    • n-gram距离
    • Jaro-Winkler距离
• 文本压缩
  • 霍夫曼编码
    • 霍夫曼树构建
    • 编码与解码
    • 最优性证明
  • 算术编码
    • 区间细分
    • 精度问题
  • Lempel-Ziv家族
    • LZ77
    • LZ78
    • Lempel-Ziv-Welch(LZW)
    • LZSS
    • LZMA
  • Burrows-Wheeler变换
    • 变换原理
    • 逆变换
    • 与DEFLATE结合
  • PPM(预测部分匹配)
    • 上下文模型
    • 逃逸符号
• 字符串索引
  • 后缀数组
    • DC3/SA-IS构建算法
    • 高度数组(LCP)
    • 应用(最长重复子串)
  • 后缀树
    • Ukkonen线性时间构建
    • McCreight算法
    • 应用(最长公共子串)
  • 后缀自动机
    • 状态构建
    • 应用场景
  • FM-Index
    • BWT索引
    • 行列采样
    • 生物信息学应用
  • 广义后缀树
    • 多字符串索引
• 正则表达式
  • NFA构建
  • DFA转换
  • Thompson算法
  • 回溯法实现
• 字符串算法应用
  • DNA序列比对
  • 拼写检查与纠正
  • 文本搜索引擎
  • 数据压缩

6. 计算几何

• 基本操作
  • 点、线、面的表示
    • 点的表示与运算
    • 向量表示
    • 线段表示
    • 多边形表示
  • 向量运算
    • 点积与叉积
    • 三重积
    • 向量投影
  • 距离计算
    • 点到点距离
    • 点到线距离
    • 点到面距离
    • 线段间距离
  • 基本判定
    • 点在线段上判定
    • 线段相交判定
    • 射线与线段相交
    • 点的方位判断
• 凸包算法
  • Graham扫描法
    • 排序技巧
    • 复杂度分析
  • Andrew算法(单调链)
    • 上下凸壳构建
    • 复杂度优势
  • Jarvis步进法(Gift wrapping)
    • 实现简单性
    • 输出敏感算法
  • 分治法
  • 快包算法(QuickHull)
  • 随机增量法
  • 剪枝优化
• 多边形
  • 多边形面积计算
    • 三角剖分法
    • 鞋带公式
  • 点在多边形内的判定
    • 射线法
    • 绕数法
    • 三角剖分法
  • 多边形相交判定
    • 分离轴定理
    • 线段相交检测
  • 多边形剖分
    • 耳切法
    • 单调多边形剖分
    • 最优三角剖分
  • 多边形核
    • 半平面交
    • 应用
  • 多边形布尔运算
    • 交、并、差操作
    • Weiler-Atherton算法
  • 简化多边形
    • Douglas-Peucker算法
• 扫描线算法
  • 线段相交
  • 矩形面积并
  • 多边形面积并
  • 最近点对
• Voronoi图
  • Fortune扫描线算法
  • 增量法
  • 分治法
  • 应用场景(最近邻查找)
• Delaunay三角剖分
  • 空圆性质
  • 翻转算法
  • 增量构造法
  • 与Voronoi图对偶关系
• 最近点对问题
  • 分治算法
  • 扫描线方法
  • 随机化算法
• 线段相交检测
  • 扫描线算法
  • Bentley-Ottmann算法
  • 分治算法
• 凸多边形算法
  • 二分查找优化
  • 切线计算
  • 支撑线
  • 凸包合并
• 计算几何高级主题
  • 几何搜索
    • 点定位问题
    • 区域查询
    • 范围树
  • 安排问题(Arrangement)
    • 线段安排
    • 双对偶性
  • 运动规划
    • 可见图
    • 元胞分解
  • 几何图形近似
  • 机器人路径规划

7. 动态规划

• 基本概念
  • 最优子结构
  • 重叠子问题
  • 备忘录法(记忆化搜索)
  • 自底向上方法
• 基本动态规划
  • 一维动态规划
    • 斐波那契序列
      • 递推实现
      • 矩阵快速幂优化
    • 最长递增子序列
      • O(n²)解法
      • O(nlogn)解法(二分优化)
      • 最长上升子序列应用
    • 最大子数组和
      • Kadane算法
      • 分治解法比较
  • 背包问题系列
    • 0-1背包问题
      • 基本实现
      • 空间优化
      • 路径重建
    • 完全背包问题
      • 基本实现
      • 与0-1背包区别
    • 多重背包问题
      • 基本实现
      • 二进制优化
      • 单调队列优化
    • 分组背包问题
    • 混合背包问题
    • 二维费用背包问题
    • 求方案数的背包问题
    • 背包方案的字典序
• 区间动态规划
  • 矩阵链乘法
    • 最优分割点
    • 方案重建
  • 最优三角剖分
    • 多边形剖分
    • 权值定义
  • 石子合并问题
    • 环形石子合并
    • 四边形不等式优化
  • 括号匹配
  • 最长回文子序列
  • 最长回文子串
  • 区间DP优化
    • 四边形不等式优化
    • Knuth优化
• 状态压缩动态规划
  • 状态表示技巧
    • 位运算基础
    • 状态转移设计
  • 旅行商问题的DP解法
    • 状态设计
    • 时空复杂度分析
  • 集合覆盖问题
    • 状态设计
    • 子集枚举技巧
  • 子集DP
    • 枚举子集的方法
    • SOS DP (Sum Over Subsets)
  • 状压技巧
    • 位操作常用技巧
    • Gosper’s Hack
    • 枚举子集的所有子集
• 树形动态规划
  • 树的最大独立集
    • 选与不选状态
    • 树上消息传递
  • 树的最小支配集
    • 状态定义
    • 转移方程设计
  • 树的最小顶点覆盖
    • 与最大独立集关系
  • 树上背包问题
    • 树上合并背包
    • DFS序优化
  • 换根DP
    • 一次DFS预处理
    • 重心的求法
  • 树上分治
    • 点分治
    • 路径计数
    • 动态点分治
  • 树链剖分
    • 重链剖分
    • 实链剖分
    • 树上路径查询

8. 贪心算法

• 贪心算法基础
  • 贪心选择性质
  • 最优子结构
  • 贪心算法证明方法
    • 交换论证
    • 反证法
• 经典贪心问题
  • 活动选择问题
    • 按结束时间排序
    • 证明正确性
  • 赫夫曼编码
    • 最优前缀码
    • 构造霍夫曼树
  • 最小生成树
    • Prim算法贪心性质
    • Kruskal算法贪心性质
  • 单源最短路径
    • Dijkstra算法贪心策略
    • 负权边的失效
  • 集合覆盖问题的贪心近似
    • 贪心算法近似比
    • 最坏情况分析
  • 作业调度问题
    • 单机最优调度
    • 最小化完成时间
    • 最小化延迟
    • 截止时间与惩罚
    • 区间调度问题
• 贪心算法设计技巧
  • 排序预处理
  • 双指针技术
  • 事件处理
  • 优先队列应用
• 贪心算法与动态规划对比
  • 相同点与差异
  • 适用场景分析
  • 常见混淆案例
• 贪心算法近似比分析
  • 近似算法概念
  • 性能保证证明
  • 近似比界限

9. 分治算法

• 分治策略基础
  • 分解、解决、合并三步法
  • 递归树分析
  • 主定理应用
• 经典分治算法
  • 快速排序
    • 分区策略
    • 随机化技巧
    • 平均时间复杂度证明
  • 归并排序
    • 合并操作
    • 稳定性分析
    • 外部排序应用
  • Strassen矩阵乘法
    • 七次乘法技巧
    • 渐近复杂度改进
    • 实际应用考量
  • 最接近点对问题
    • 平面划分
    • 条带内点对处理
    • 线性时间合并
  • 快速选择(第k小元素)
    • 分区后直接递归
    • 期望线性时间证明
    • 中位数的中位数(BFPRT)算法
  • 循环赛日程表问题
    • 递归构造
    • 应用场景
  • 大整数乘法
    • Karatsuba算法
    • 分治策略减少乘法次数
• 分治算法设计与优化
  • 平衡分割
  • 合并步骤优化
  • 基本情况优化
  • 避免重复计算
• 分治与动态规划的结合
  • 分治+记忆化
  • 区间DP的分治理解

10. 回溯算法

• 回溯法基础
  • 状态空间树
  • 显式与隐式约束
  • 解空间构建
  • 剪枝策略
• 经典回溯问题
  • N皇后问题
    • 约束传播
    • 位运算优化
    • 对称性剪枝
  • 图的着色问题
    • 最小着色数
    • 冲突检测优化
    • 启发式选择策略
  • 子集和问题
    • 排序预处理
    • 剪枝条件
    • 与动态规划对比
  • 汉密尔顿路径问题
    • 可行性剪枝
    • 与TSP关系
  • 数独求解
    • 约束传播
    • 最小剩余值启发式
    • 舞蹈链算法(DLX)
  • 组合问题生成
    • 子集生成
    • 排列生成
    • 组合生成
    • 字典序生成算法
• 回溯优化技巧
  • 顺序选择优化
  • 约束传播
  • 对称性破缺
  • 位向量表示状态
  • 预排序
  • 预处理
• 启发式回溯
  • 启发函数设计
  • 剪枝策略
  • 结合局部搜索
• 回溯与分支定界
  • 界限函数设计
  • 最优解搜索
  • 剪枝效率分析

11. 随机化算法

• 随机算法基础
  • 概率空间
  • 随机变量
  • 期望与方差
  • 随机算法类型
    • 蒙特卡洛算法
    • 拉斯维加斯算法
    • 舍伍德算法
• 随机化技术
  • 随机采样
  • 随机置换
  • 随机选择
  • 随机分区
  • 随机行走
• 经典随机化算法
  • 随机快速排序
    • 随机主元选择
    • 期望时间分析
  • 随机化素性测试
    • Miller-Rabin算法
      • 二次探测
      • 错误概率分析
    • Fermat素性测试
      • 小费马定理
      • Carmichael数的弱点
    • Solovay-Strassen算法
    • AKS确定性素性测试
  • 蒙特卡洛算法
    • 随机近似算法
    • π值估计
    • 面积计算
    • 积分估计
  • 拉斯维加斯算法
    • 随机快速排序
    • 随机化BST
  • 舍伍德算法
    • 完美洗牌
    • Fisher-Yates算法
  • 快速随机选择算法
    • 期望线性时间分析
    • 与确定性选择对比
  • 最小割算法
    • Karger算法
    • Karger-Stein算法
    • 期望分析
• 随机化数据结构
  • 跳表
    • 概率层次构建
    • 期望查找时间
  • 树状随机化结构
    • Treap(树堆)
    • 随机化二叉搜索树
  • 布隆过滤器
    • 错误率分析
    • 最优参数选择
  • Count-Min Sketch
  • HyperLogLog算法
• 随机化在线算法
  • 随机化竞争分析
  • 对抗输入处理
• 随机化算法的去随机化
  • 条件期望方法
  • 方法德兰多米化
  • 伪随机函数应用

12. 数论算法

• 基本数论概念
  • 整除性与同余
  • 素数与合数
  • 算术基本定理
  • 模运算性质
• 整数运算
  • 高精度整数计算
    • 大整数加减
    • 大整数乘法
      • 普通乘法
      • Karatsuba算法
      • FFT/NTT优化
    • 大整数除法
  • 最大公约数(GCD)
    • 欧几里得算法
      • 基本算法
      • 时间复杂度分析
      • 二进制优化(Binary GCD)
    • 扩展欧几里得算法
      • 求解线性丢番图方程
      • 模逆元计算
    • Stein算法(二进制GCD)
      • 位运算优化
  • 最小公倍数(LCM)
    • GCD关系
    • 多个数的LCM计算
• 素数与因数分解
  • 素数生成与判定
    • 试除法
    • 埃拉托斯特尼筛法
      • 基本筛法
      • 优化技巧
    • 线性筛法
      • 欧拉筛
      • 时间复杂度优化
    • 区间筛法
    • 素性测试
      • Miller-Rabin测试
      • Fermat测试
  • 整数分解
    • 试除法
    • Pollard’s rho算法
    • Pollard’s p-1算法
    • 二次筛法
    • 数域筛法
• 模运算
  • 模运算基本性质
  • 快速幂
    • 二进制快速幂
    • 矩阵快速幂
    • 多项式快速幂
  • 模逆元
    • 扩展欧几里得法
    • 费马小定理法
    • 线性预处理
  • 中国剩余定理
    • 基本定理
    • 扩展中国剩余定理
    • 应用场景
  • 离散对数
    • Shanks的Baby-step Giant-step算法
    • Pollard’s rho算法
    • 指标计算法
• 数论函数
  • 欧拉函数
    • 性质
    • 计算方法
    • 欧拉定理
  • 莫比乌斯函数
    • 定义与性质
    • 莫比乌斯反演
    • 计算技巧
  • 数论函数的卷积
• 连分数
  • 连分数展开
  • 有理数逼近
• 密码学应用
  • RSA算法基础
    • 公钥生成
    • 加密解密过程
    • 安全性分析
  • Diffie-Hellman密钥交换
  • 离散对数问题
  • 素数在密码学中的应用

13. 计算复杂性理论

• 复杂度分析基础
  • 渐近记号
    • Big-O, Big-Omega, Big-Theta
    • 小o, 小omega
    • 渐近紧确界
  • 时间复杂度分析
    • 最坏情况分析
    • 平均情况分析
    • 摊销分析
      • 聚集法
      • 核算法
      • 势能法
  • 空间复杂度分析
    • 递归栈空间
    • 辅助空间
• 复杂度类别
  • P类
    • 多项式时间可解问题
    • 常见P类问题
  • NP类
    • 非确定性多项式时间
    • 验证与求解的区别
  • NP完全
    • Cook-Levin定理
    • 归约概念
    • NP完全性证明技术
  • NP难问题
    • 与NP完全的关系
    • 优化问题与判定问题
  • PSPACE
  • 可数性与不可数性
  • 决定性问题
• 经典NP完全问题
  • 布尔可满足性问题(SAT)
    • 3-SAT
    • Horn-SAT
  • 旅行商问题
    • 判定版本
    • 优化版本
    • 近似算法
  • 顶点覆盖问题
    • 2-近似算法
    • 证明思路
  • 集合覆盖问题
    • 贪心近似算法
    • 近似比
  • 子集和问题
    • 伪多项式时间算法
    • NP完全性证明
  • 图着色问题
    • k-着色
    • 近似算法
  • 团问题(Clique)
  • 独立集问题
• 近似算法
  • 近似比
  • 近似方案(PTAS)
  • 完全近似方案(FPTAS)
  • 不可近似性
  • 经典近似算法
    • 装箱问题近似
    • TSP近似
    • 顶点覆盖近似
• 随机化与平均复杂度
  • 随机复杂度分析
  • 平滑分析
• 量子计算简介
  • 量子复杂度类BQP
  • 量子多项式时间
  • 量子算法概览

14. 调度与负载均衡算法

• 调度问题基础
  • 任务与资源模型
  • 调度目标
  • 在线与离线调度
  • 抢占式与非抢占式调度
• 基本轮询算法
  • 简单轮询(Round Robin)
    • 基本实现
    • 均衡性分析
    • 适用场景
  • 加权轮询(Weighted Round Robin)
    • 权重分配策略
    • 实现技巧
  • 平滑加权轮询(Smooth Weighted Round Robin)
    • 动态权重调整
    • 平滑性保证
  • 交替轮询(Alternating RR)
• 高级负载均衡
  • 最少连接(Least Connection)
    • 连接计数
    • 新连接分配
  • 加权最少连接(Weighted Least Connection)
    • 加权因子设计
  • 最短响应时间
    • 响应时间估计
    • 自适应调整
  • IP哈希(IP Hash)
    • 一致性考虑
    • 应用场景
  • 一致性哈希(Consistent Hashing)
    • 哈希环设计
    • 虚拟节点
    • 平衡性分析
    • 最小化迁移
  • 动态负载均衡
    • 服务器状态监控
    • 负载预测
    • 自适应调整
• 进程/线程调度
  • 操作系统调度
    • 先来先服务(FCFS)
      • 实现方法
      • 优缺点分析
    • 短作业优先(SJF)
      • 非抢占式SJF
      • 抢占式SJF(SRTF)
      • 预估执行时间
    • 优先级调度
      • 静态优先级
      • 动态优先级
      • 老化技术
    • 轮转调度(Round Robin)
      • 时间片选择
      • 上下文切换开销
    • 多级队列调度
      • 队列分配策略
      • 队列间调度
    • 多级反馈队列
      • 动态优先级调整
      • 时间片增长策略
    • 完全公平调度(CFS)
      • 虚拟运行时间
      • 红黑树实现
      • 调度延迟与粒度
  • 实时调度算法
    • 速率单调调度(RMS)
      • 最优性证明
      • 可调度性分析
    • 最早截止时间优先(EDF)
      • 动态优先级
      • 最优性证明
    • 最小松弛时间优先(LLF)
      • 计算方法
      • 实现复杂度
• 作业调度高级主题
  • 随机工作窃取(Work Stealing)
    • 双端队列设计
    • 窃取策略
    • 负载均衡性质
  • 分支定界作业调度
    • 界限函数设计
    • 分支策略
  • 遗传算法作业调度
    • 编码设计
    • 适应度函数
    • 交叉与变异
  • 强化学习调度方法
    • 状态与动作设计
    • 奖励函数
    • 训练策略
  • 资源受限项目调度(RCPSP)
    • 数学模型
    • 启发式算法
  • 作业车间调度问题
    • 流水作业调度
      • Johnson算法(两台机器)
      • NEH算法
    • 开放式作业调度
    • 作业车间调度
      • 关键路径方法
      • 瓶颈机器识别
  • 批处理作业调度
    • 批量形成策略
    • 批内调度

15. 机器学习算法

• 监督学习
  • 线性模型
    • 线性回归
      • 最小二乘法
      • 梯度下降
      • 正则化技术
    • 逻辑回归
      • 极大似然估计
      • 决策边界
      • 多分类扩展
    • 感知器
      • 在线学习
      • 收敛性证明
  • 决策树
    • 构建算法
      • ID3算法
      • C4.5算法
      • CART算法
    • 特征选择
      • 信息增益
      • 增益率
      • 基尼指数
    • 剪枝策略
      • 预剪枝
      • 后剪枝
    • 处理连续特征
  • 集成学习
    • Bagging
      • 随机森林
        • 随机特征选择
        • OOB错误估计
        • 特征重要性
    • Boosting
      • AdaBoost
        • 样本权重调整
        • 弱分类器权重
      • Gradient Boosting
        • GBDT
        • XGBoost
        • LightGBM
      • Stacking
    • 投票方法
  • 支持向量机(SVM)
    • 线性SVM
      • 最大间隔
      • 对偶问题
      • SMO算法
    • 核方法
      • 多项式核
      • 高斯核(RBF)
      • 字符串核
    • 支持向量回归
    • 一类SVM
  • k-近邻算法(KNN)
    • 距离度量
      • 欧氏距离
      • 曼哈顿距离
      • 闵可夫斯基距离
    • 加权策略
    • k值选择
    • 邻近搜索优化
      • kd树
      • 球树
      • 局部敏感哈希
  • 神经网络基础
    • 多层感知机
      • 前向传播
      • 反向传播
      • 激活函数
    • 损失函数
      • 均方误差
      • 交叉熵
    • 优化算法
      • SGD
      • Adam
      • RMSprop
    • 正则化技术
      • Dropout
      • 批标准化
• 无监督学习
  • 聚类算法
    • k-均值聚类
      • 算法步骤
      • 初始中心选择
      • k值确定
      • k-means++
      • Mini-batch k-means
    • 层次聚类
      • 凝聚方法
      • 分裂方法
      • 连接策略
        • 单连接
        • 全连接
        • 平均连接
        • Ward方法
    • 密度聚类
      • DBSCAN
        • 核心点、边界点与噪声
        • 参数选择
      • OPTICS
      • Mean Shift
    • 谱聚类
      • 拉普拉斯矩阵
      • 特征向量
    • 高斯混合模型
      • EM算法
      • 模型选择
  • 降维技术
    • 主成分分析(PCA)
      • 协方差矩阵
      • 特征值分解
      • 贡献率分析
      • 核PCA
    • 线性判别分析(LDA)
      • 类内散度与类间散度
      • 特征抽取
    • 奇异值分解(SVD)
      • 矩阵分解原理
      • 截断SVD
      • 应用(推荐系统)
    • 流形学习
      • ISOMAP
      • t-SNE
      • UMAP
  • 异常检测
    • 统计方法
    • 基于距离
    • 基于密度
    • 孤立森林
  • 关联规则挖掘
    • Apriori算法
    • FP-Growth算法
• 强化学习
  • 基本概念
    • 马尔可夫决策过程
    • 状态、动作、奖励
    • 值函数与策略
  • 经典算法
    • 动态规划方法
      • 策略迭代
      • 值迭代
    • 蒙特卡洛方法
      • 首次访问MC
      • 每次访问MC
    • 时序差分学习
      • SARSA
        • on-policy学习
        • 期望SARSA
      • Q-learning
        • off-policy学习
        • Double Q-learning
    • 策略梯度法
      • REINFORCE算法
      • Actor-Critic方法
    • 深度强化学习
      • DQN
      • A3C
      • PPO
  • 探索与利用
    • ε-greedy
    • UCB
    • Thompson采样
  • 多臂赌博机问题
    • 算法对比
    • 上下文赌博机
• 半监督与迁移学习
  • 半监督学习
    • 自训练
    • 协同训练
    • 图方法
  • 迁移学习
    • 领域自适应
    • 微调技术
• 机器学习评估方法
  • 交叉验证
  • 数据集划分
  • 评价指标
  • 过拟合与欠拟合
  • 偏差-方差分解

16. 分布式算法

• 分布式系统模型
  • 同步与异步模型
  • 故障模型
  • 一致性模型
  • CAP定理
• 分布式共识
  • 二阶段提交(2PC)
  • 三阶段提交(3PC)
  • Paxos算法
    • Basic Paxos
    • Multi-Paxos
    • 活锁问题
  • Raft算法
    • 领导选举
    • 日志复制
    • 安全性证明
    • 成员变更
  • ZAB协议(Zookeeper)
  • 拜占庭将军问题
    • 拜占庭容错(BFT)
    • PBFT算法
    • Tendermint
  • 区块链共识
    • PoW(工作量证明)
    • PoS(权益证明)
    • DPoS(委托权益证明)
• 分布式哈希表
  • Chord
    • 环形结构
    • 指针表优化
  • Pastry
  • Kademlia
    • XOR距离
    • k-bucket
  • 应用(P2P网络)
• 一致性哈希
  • 虚拟节点
  • 负载均衡
  • 最小化迁移
  • 应用场景(分布式缓存)
• 分布式计算
  • MapReduce
    • 编程模型
    • 容错机制
    • 调度策略
  • Spark计算模型
    • RDD抽象
    • 转换与动作
    • DAG执行引擎
    • 内存计算优势
  • 流处理
    • Storm
    • Flink
    • 窗口计算
  • 批处理与流处理统一
• 分布式锁
  • 基于数据库
  • 基于缓存
    • Redis实现
    • 锁超时问题
  • 基于ZooKeeper
  • 死锁检测与预防
• 分布式事务
  • ACID特性
  • BASE理论
  • 分布式事务协议
    • 2PC/3PC
    • TCC(Try-Confirm-Cancel)
    • SAGA模式
  • 最终一致性
• 分布式系统设计模式
  • 主从复制
  • 读写分离
  • 分区(Sharding)
  • 一致性哈希
  • 领导选举
  • 背压机制
  • 熔断器模式
• 分布式系统理论
  • FLP不可能性
  • CAP定理
  • PACELC定理
  • 一致性级别

17. 并行算法

• 并行计算模型
  • PRAM模型
  • BSP模型
  • LogP模型
  • 并行复杂度分析
    • 加速比
    • 效率
    • Amdahl定律
    • Gustafson定律
• 并行编程范式
  • 共享内存
    • OpenMP
    • pthread
  • 消息传递
    • MPI
  • 数据并行
    • SIMD
    • GPU编程模型
      • CUDA
      • OpenCL
• 并行算法设计技术
  • 分解与映射
  • 局部性优化
  • 负载均衡
  • 通信优化
  • 同步机制
• 并行排序
  • 并行归并排序
    • 递归并行
    • 工作划分
  • 并行快速排序
    • 划分策略
    • 任务分配
  • 样本排序
  • 基数排序并行化
  • 位图排序并行化
• 并行图算法
  • 并行广度优先搜索
    • 前沿扩展
    • 层同步
    • 工作分配
  • 并行深度优先搜索
  • 并行最短路径
    • 并行Dijkstra
    • 并行Bellman-Ford
    • Δ-stepping算法
  • 并行最小生成树
  • 并行连通分量
    • Shiloach-Vishkin算法
    • 标签传播
• 并行矩阵运算
  • 矩阵乘法
    • 块分割
    • Cannon算法
    • SUMMA算法
    • DNS算法
  • 矩阵分解并行化
    • 并行LU分解
    • 并行Cholesky分解
    • 并行QR分解
  • 求解线性方程组
    • 并行高斯消元
    • 迭代方法并行化
• 并行动态规划
  • 依赖图分析
  • 波前并行
  • k-D格栅方法
• 并行前缀和
  • Hillis-Steele算法
  • Blelloch算法
  • 效率分析
• 工作窃取调度
  • 双端队列设计
  • 窃取策略
  • 负载均衡
  • 应用(并行递归)
• 并行数值算法
  • 并行FFT
  • 并行数值积分
  • 并行随机数生成
• 并行机器学习
  • 数据并行
  • 模型并行
  • 梯度并行化
  • 参数服务器架构

18. 压缩算法

• 压缩基础
  • 压缩比
  • 香农信息论
  • 熵编码原理
  • 信源模型
• 无损压缩
  • 基本无损压缩
    • 游程编码(RLE)
      • 基本编码方案
      • 变长RLE
      • 应用场景(图像)
    • 霍夫曼编码
      • 前缀码特性
      • 霍夫曼树构建
      • 自适应霍夫曼编码
      • 规范霍夫曼编码
    • 算术编码
      • 区间细分
      • 精度问题处理
      • 与霍夫曼编码比较
    • 预测编码
      • 差分编码
      • DPCM(差分脉冲编码调制)
    • 字典编码
      • LZ77/LZSS
        • 滑动窗口
        • 前向缓冲区
        • 匹配查找优化
      • LZ78/LZW
        • 字典构建
        • 编码过程
        • 解码过程
        • GIF压缩应用
      • DEFLATE
        • LZ77与霍夫曼结合
        • 静态与动态霍夫曼树
        • zlib/gzip实现
      • LZMA
        • 改进的匹配查找
        • 范围编码器
        • 7z格式
  • 有损压缩
    • 变换编码
      • 离散余弦变换(DCT)
        • 二维DCT
        • 能量聚集性
        • JPEG应用
      • 小波变换
        • 多分辨率分析
        • 离散小波变换
        • JPEG2000应用
      • 分形压缩
        • 迭代函数系统
        • 自相似性利用
    • 量化
      • 标量量化
      • 向量量化
      • 自适应量化
    • 预测编码
      • 运动补偿
      • 视频编码应用
    • 感知编码
      • 人类视觉系统模型
      • 掩蔽效应利用
  • 特定领域压缩
    • 图像压缩
      • JPEG
        • 编码流程
        • 质量控制
      • PNG
        • 无损特性
        • 滤波器优化
      • WebP
      • JPEG-XL
    • 视频压缩
      • H.264/AVC
      • H.265/HEVC
      • VP9
      • AV1
    • 音频压缩
      • MP3
      • AAC
      • Vorbis
      • Opus
    • 文本压缩
      • bzip2
      • PPM
      • 上下文模型
  • 压缩算法评估
    • 压缩率
    • 速度考量
    • 对称性分析
    • 内存需求
    • 错误鲁棒性

19. 密码学算法

• 密码学基础
  • 信息安全基本原则
    • 保密性
    • 完整性
    • 可用性
    • 不可否认性
  • 攻击模型
    • 唯密文攻击
    • 已知明文攻击
    • 选择明文攻击
    • 选择密文攻击
  • 密码学原语
    • 伪随机生成器
    • 单向函数
    • 单向陷门函数
    • 承诺方案
• 对称加密
  • 流密码
    • RC4
      • 密钥调度算法
      • 伪随机生成算法
      • 已知弱点
    • ChaCha20
      • 四分之一轮函数
      • Salsa20改进
    • 线性反馈移位寄存器(LFSR)
      • 最大长度序列
      • 非线性组合
  • 分组密码
    • DES
      • Feistel网络
      • S盒设计
      • 密钥调度
      • 3DES变种
    • AES
      • SPN结构
      • 字节替代
      • 行移位
      • 列混合
      • 轮密钥加
      • 密钥扩展
    • 其他主要分组密码
      • Blowfish
      • Twofish
      • Serpent
      • IDEA
  • 操作模式
    • ECB模式
    • CBC模式
    • CFB模式
    • OFB模式
    • CTR模式
    • GCM模式
    • XTS模式
  • 认证加密
    • AEAD模式
    • GCM
    • CCM
    • EAX
    • ChaCha20-Poly1305
• 非对称加密
  • 数学基础
    • 模运算
    • 离散对数问题
    • 因数分解问题
    • 椭圆曲线离散对数
  • RSA
    • 密钥生成
    • 加密解密过程
    • 签名验证
    • 填充方案(PKCS#1)
    • 安全性考量
  • ElGamal
    • 基于离散对数
    • 同态性质
  • ECC(椭圆曲线加密)
    • 椭圆曲线基本概念
    • 点加法与倍乘
    • ECDH(椭圆曲线Diffie-Hellman)
    • ECDSA(椭圆曲线数字签名)
    • EdDSA(Edwards曲线数字签名)
  • Diffie-Hellman密钥交换
    • 原始协议
    • 中间人攻击防护
    • 有限域实现
    • 椭圆曲线实现
  • 格密码
    • 格基础知识
    • LWE问题
    • NTRU
    • 后量子密码学
• 哈希函数
  • 哈希函数性质
    • 单向性
    • 抗碰撞性
    • 雪崩效应
  • 构造方法
    • Merkle-Damgård结构
    • 海绵结构
  • 实际哈希函数
    • MD5
      • 压缩函数设计
      • 已知攻击
    • SHA家族
      • SHA-1
      • SHA-2
      • SHA-3(Keccak)
    • BLAKE2
      • BLAKE2b/BLAKE2s
      • 并行化特性
    • RIPEMD
    • Whirlpool
  • 密码学应用
    • 消息认证码(HMAC)
    • 密钥派生函数(KDF)
    • 随机数生成
• 数字签名
  • 签名方案
    • RSA签名
    • DSA
    • ECDSA
    • EdDSA(Ed25519)
    • Schnorr签名
  • 盲签名
  • 群签名
  • 环签名
  • 多重签名
  • 聚合签名
• 消息认证码
  • HMAC
  • CBC-MAC
  • PMAC
  • CMAC
  • Poly1305
• 零知识证明
  • 基本概念
    • 完备性
    • 可靠性
    • 零知识性
  • 交互式证明
    • Schnorr协议
    • Fiat-Shamir变换
  • 非交互式零知识证明
    • zk-SNARKs
    • zk-STARKs
    • Bulletproofs
  • 应用
    • 身份验证
    • 匿名凭证
    • 区块链隐私
• 密钥管理
  • 密钥生成
  • 密钥分发
  • 密钥存储
  • 公钥基础设施(PKI)
    • 证书
    • CA层次结构
    • 吊销机制
• 密码协议
  • TLS/SSL
  • SSH
  • 安全多方计算
  • 秘密共享
    • Shamir门限方案
    • Blakley方案
  • 同态加密
    • 部分同态
    • 全同态
    • 应用场景

20. 优化算法

• 优化问题基础
  • 问题形式化
  • 可行域与目标函数
  • 局部最优与全局最优
  • 凸优化基础
• 线性规划
  • 标准形式与松弛形式
  • 几何解释
  • 基本解与基本可行解
  • 单纯形法
    • 初始基可行解
    • 旋转操作
    • 退化与循环性
    • 两阶段法
    • 大M法
  • 内点法
    • 障碍函数方法
    • 原对偶方法
    • 复杂度优势
  • 对偶理论
    • 弱对偶性
    • 强对偶性
    • 互补松弛性
    • 对偶单纯形法
  • 整数线性规划
    • 分支定界法
    • 割平面法
    • 列生成法
  • 网络流线性规划
    • 最小费用流
    • 运输问题
    • 指派问题
• 非线性优化
  • 无约束优化
    • 梯度下降法
      • 步长选择
      • 收敛性分析
      • 随机梯度下降
      • 批量梯度下降
      • mini-batch梯度下降
    • 牛顿法
      • 二阶信息利用
      • 收敛速度
      • 计算复杂度
    • 拟牛顿法
      • BFGS
      • L-BFGS
      • DFP
      • SR1
    • 共轭梯度法
      • Fletcher-Reeves公式
      • Polak-Ribière公式
    • 信赖域方法
    • 线搜索方法
      • Armijo准则
      • Wolfe条件
      • 黄金分割法
  • 约束优化
    • 拉格朗日乘数法
    • KKT条件
    • 惩罚函数法
    • 障碍函数法
    • 增广拉格朗日法
    • 序列二次规划(SQP)
  • 全局优化
    • 多起点局部搜索
    • 分支定界
    • 区间分析
• 组合优化
  • 精确算法
    • 分支定界法
      • 下界计算
      • 分支策略
      • 搜索策略
    • 动态规划
    • 背包问题算法
    • 最短路径算法
  • 近似算法
    • 近似度量
    • 近似方案设计
    • 集合覆盖近似
    • TSP近似
  • 启发式与元启发式
    • 局部搜索
      • 爬山法
      • 模拟退火
        • 退火调度
        • 邻域定义
        • 接受准则
      • 禁忌搜索
        • 禁忌表
        • 短期记忆
        • 长期记忆
    • 进化算法
      • 遗传算法
        • 编码方案
        • 选择操作
        • 交叉操作
        • 变异操作
        • 参数设置
      • 进化策略
      • 差分进化
      • 遗传编程
    • 群体智能
      • 粒子群优化
        • 粒子更新
        • 邻域结构
        • 收敛性分析
      • 蚁群算法
        • 信息素更新
        • 状态转移规则
        • TSP应用
      • 人工蜂群
      • 萤火虫算法
      • 和声搜索
    • 路径重连
    • 变邻域搜索
• 多目标优化
  • Pareto最优概念
  • 加权求和法
  • 约束法
  • 非支配排序
  • 多目标进化算法
    • NSGA-II
    • MOEA/D
  • 指标法
• 鲁棒优化
  • 不确定集建模
  • 最坏情况优化
  • 分布式鲁棒优化
• 在线优化与学习
  • 多臂赌博机问题
  • 在线凸优化
  • 专家建议问题
  • 在线学习理论
• 优化算法应用
  • 机器学习中的优化
  • 运筹学应用
  • 金融优化
  • 工程设计优化

21. 数据库算法

• 数据库基础
  • 数据模型
  • 关系代数
  • 事务特性(ACID)
  • 并发控制
  • 故障恢复
• 索引结构
  • B+树索引
    • 结构特性
    • 插入算法
    • 删除算法
    • 范围查询优化
    • 缓冲池管理
  • 哈希索引
    • 静态哈希
    • 动态哈希
      • 可扩展哈希
      • 线性哈希
    • 多级哈希
    • 部分匹配查询
  • 全文索引
    • 倒排索引
      • 词项管理
      • 倒排列表
      • 压缩技术
    • n-gram索引
    • 后缀数组索引
    • 词典树索引
    • 向量空间模型
    • BM25排序
  • 空间索引
    • R树家族
      • R树
      • R*树
      • R+树
    • 四叉树/八叉树
    • 网格文件
    • 空间填充曲线
    • 地理哈希
  • 多维索引
    • kd树
    • UB树
    • 位图索引
    • 联合索引
    • 前缀压缩
• 查询优化
  • 查询处理步骤
    • 解析
    • 重写
    • 优化
    • 执行
  • 基于规则的优化
    • 谓词下推
    • 投影下推
    • 连接重排序
    • 常量传播
  • 基于成本的优化
    • 统计信息收集
    • 成本模型
    • 选择率估计
    • 直方图技术
  • 连接算法
    • 嵌套循环连接
      • 简单嵌套循环
      • 索引嵌套循环
      • 块嵌套循环
    • 排序合并连接
      • 预排序优化
    • 哈希连接
      • 基本哈希连接
      • Grace哈希连接
      • Hybrid哈希连接
    • 半连接
    • 特殊连接
      • 自然连接
      • 外连接算法
      • 反连接
    • 多表连接优化
      • 连接顺序选择
      • 左深树与右深树
      • 动态规划方法
  • 排序算法
    • 外部归并排序
    • 多路合并
    • 置换选择算法
    • TOP-N优化
    • 排序回避技术
  • 聚合算法
    • 哈希聚合
    • 排序聚合
    • 分组优化
  • 查询执行
    • 火山模型
    • 向量化执行
    • 代码生成
    • 并行执行
• 事务处理
  • 并发控制协议
    • 锁机制
      • 两阶段锁协议
      • 死锁处理
      • 锁粒度
      • 意向锁
    • MVCC
      • 时间戳排序
      • 快照隔离
      • 版本链管理
      • 垃圾回收
    • 乐观并发控制
      • 验证技术
    • 2PC/3PC
      • 协调者逻辑
      • 参与者逻辑
      • 故障处理
    • 分布式事务
      • XA协议
      • SAGA模式
  • 隔离级别
    • 读未提交
    • 读已提交
    • 可重复读
    • 可序列化
    • 异常现象处理
  • 故障恢复
    • WAL(预写式日志)
    • REDO
    • UNDO
    • 检查点
    • 恢复算法
      • ARIES
• 数据仓库算法
  • 物化视图
    • 视图选择
    • 增量维护
    • 视图匹配
  • OLAP操作
    • 多维数据模型
    • 上卷与下钻
    • 切片与切块
  • 数据立方体计算
    • 预计算策略
    • BUC算法
    • Star Cubing
• 数据压缩
  • 行压缩
  • 列压缩
    • 字典编码
    • 游程编码
    • 差分编码
    • 位图编码
  • 索引压缩
  • 压缩与查询执行
• 数据库中间件算法
  • 分库分表
    • 水平分片
    • 垂直分片
    • 路由算法
  • 负载均衡
  • 分布式查询处理
  • 连接查询路由
• 流数据处理
  • 窗口计算
  • 近似算法
    • 计数器
    • Bloom过滤器
    • Count-Min Sketch
    • HyperLogLog
  • 连续查询处理
  • 流连接算法

22. 区块链算法

• 区块链基础
  • 分布式账本
  • 哈希链结构
  • 交易验证
  • 共识机制概念
• 共识算法
  • 工作量证明(PoW)
    • 哈希算法
    • 难度调整
    • 51%攻击防御
    • 比特币挖矿
  • 权益证明(PoS)
    • 质押机制
    • 验证者选择
    • 惩罚机制
    • 以太坊2.0实现
  • 委托权益证明(DPoS)
    • 代表选举
    • 区块生产
    • EOS实现
  • 实用拜占庭容错(PBFT)
    • 三阶段协议
    • 视图更换
    • 超级账本实现
  • 其他共识机制
    • PoA(权威证明)
    • PoB(燃烧证明)
    • PoC(容量证明)
    • Avalanche
• 密码学原语
  • 哈希函数应用
    • 区块链中的Merkle树
    • 工作量证明算法
  • 数字签名
    • ECDSA应用
    • 多重签名
    • 环签名
    • 盲签名
    • 聚合签名
  • 零知识证明
    • Zcash中的zk-SNARKs
    • 零知识应用场景
• 智能合约
  • 执行环境
  • 合约语言
  • 气体计费机制
  • 合约验证
  • 合约优化
• 区块链存储
  • Merkle树
    • 树构建
    • 简化支付验证
  • Merkle Patricia树
    • 以太坊状态存储
  • IPFS存储
  • DAG结构
    • IOTA Tangle
    • Hashgraph
• 区块链安全算法
  • 防双花机制
  • 防重放攻击
  • 密钥管理
  • 闪电网络
    • 支付通道
    • 路由算法
  • 跨链技术
    • 原子交换
    • 哈希时间锁定合约