一、排序算法问题
#
1. 比较排序算法
#
- 冒泡排序原理与优化
- 选择排序的实现与分析
- 插入排序及其变种
- 希尔排序的增量序列
- 归并排序的分治策略
- 快速排序的划分方法
- 堆排序的建堆过程
2. 非比较排序算法
#
- 计数排序的适用条件
- 桶排序的桶设计原则
- 基数排序的位数处理
3. 排序算法性能分析
#
- 时间复杂度理论分析
- 空间复杂度比较
- 稳定性讨论
- 实际应用场景选择
二、搜索算法问题
#
1. 基本搜索算法
#
- 线性搜索的实现
- 二分查找的前提条件
- 插值搜索的原理
2. 图搜索算法
#
- 深度优先搜索(DFS)
- 广度优先搜索(BFS)
- 双向搜索优化
- 迭代加深搜索
3. 启发式搜索
#
- A*算法与启发函数
- 最佳优先搜索
- 束搜索(Beam Search)
三、图论算法问题
#
1. 最短路径问题
#
- Dijkstra算法原理
- Bellman-Ford算法
- Floyd-Warshall算法
- SPFA算法优化
2. 最小生成树
#
- Prim算法实现
- Kruskal算法与并查集
- 次小生成树问题
3. 网络流问题
#
四、动态规划问题
#
1. 经典动态规划模型
#
- 背包问题系列
- 最长公共子序列
- 矩阵链乘法
- 编辑距离问题
2. 状态设计技巧
#
3. 树形动态规划
#
五、字符串算法问题
#
1. 字符串匹配
#
- KMP算法原理
- BM算法优化
- Sunday算法
- 多模式匹配
2. 字符串处理
#
- 字典树(Trie)应用
- AC自动机构建
- 后缀数组构造
- 后缀自动机
六、数论与组合问题
#
1. 基础数论问题
#
- 素数判定与筛法
- 最大公约数算法
- 模运算与逆元
- 中国剩余定理
2. 组合数学问题
#
- 排列组合计数
- 容斥原理应用
- 生成函数方法
- Polya计数定理
七、计算几何问题
#
1. 基本几何运算
#
- 点、线、面关系判断
- 凸包算法
- 最近点对问题
- 多边形面积计算
2. 高级几何问题
#
- 半平面交算法
- 旋转卡壳技术
- Voronoi图构造
- 三角剖分方法
八、NP难问题与近似算法
#
1. 经典NP完全问题
#
- 旅行商问题(TSP)
- 集合覆盖问题
- 顶点覆盖问题
- 背包问题的NP完全性
2. 近似算法设计
#
- 贪心近似算法
- 线性规划舍入
- 随机化算法
- 局部搜索方法
九、并行与分布式算法
#
1. 并行计算模型
#
- PRAM模型
- MapReduce框架
- 并行排序算法
- 并行图算法
2. 分布式算法问题
#
- 一致性算法
- 领导者选举
- 分布式排序
- 拜占庭将军问题
十、在线算法与流算法
#
1. 在线算法设计
#
- 竞争分析理论
- 页面置换算法
- 在线负载均衡
- 在线匹配问题
2. 数据流算法
#
十一、随机算法问题
#
1. 随机化算法类型
#
- Las Vegas算法
- Monte Carlo算法
- 随机游走算法
- 随机舍入技术
2. 概率分析
#
- 期望时间复杂度
- 高概率分析
- 鞅与停时定理
- 随机过程应用
十二、高级数据结构问题
#
1. 平衡树结构
#
- AVL树旋转操作
- 红黑树性质
- B树与B+树
- 伸展树摊还分析
2. 特殊数据结构
#
- 跳表随机化构造
- 并查集路径压缩
- 线段树区间操作
- 树状数组应用