{< katex />}

算法基础

一、算法概述 #

1.1 算法定义与特征 #

• 算法的基本概念
• 算法的五大特性
• 算法与程序的区别
• 算法的重要性

1.2 算法分析基础 #

• 时间复杂度分析
• 空间复杂度分析
• 渐进表示法
• 最好、最坏和平均情况分析

1.3 算法设计方法 #

• 分治法
• 动态规划
• 贪心算法
• 回溯法
• 分支限界法

二、数据结构基础 #

2.1 线性结构 #

• 数组与链表
• 栈与队列
• 字符串处理
• 哈希表

2.2 树形结构 #

• 二叉树
• 二叉搜索树
• 平衡二叉树
• 堆与优先队列

2.3 图结构 #

• 图的表示方法
• 图的遍历算法
• 最短路径问题
• 最小生成树

三、排序算法 #

3.1 比较排序 #

• 冒泡排序
• 选择排序
• 插入排序
• 希尔排序

3.2 高效排序 #

• 快速排序
• 归并排序
• 堆排序
• 排序算法比较

3.3 非比较排序 #

• 计数排序
• 基数排序
• 桶排序
• 外部排序

四、搜索算法 #

4.1 基本搜索 #

• 顺序搜索
• 二分搜索
• 插值搜索
• 斐波那契搜索

4.2 树搜索 #

• 二叉搜索树操作
• AVL树搜索
• 红黑树搜索
• B树与B+树

4.3 图搜索 #

• 深度优先搜索
• 广度优先搜索
• A*搜索算法
• 启发式搜索

五、动态规划 #

5.1 基础理论 #

• 最优子结构
• 重叠子问题
• 状态转移方程
• 记忆化技术

5.2 经典问题 #

• 背包问题
• 最长公共子序列
• 矩阵链乘法
• 编辑距离

5.3 应用实例 #

• 最短路径问题
• 资源分配问题
• 序列比对
• 股票交易问题

六、贪心算法 #

6.1 基本原理 #

• 贪心选择性质
• 最优子结构
• 贪心算法证明
• 贪心与动态规划比较

6.2 典型应用 #

• 活动选择问题
• 霍夫曼编码
• 最小生成树算法
• 单源最短路径

七、图论算法 #

7.1 连通性 #

• 连通分量
• 强连通分量
• 关节点与桥
• 双连通分量

7.2 网络流 #

• 最大流问题
• 最小割问题
• 费用流问题
• 匹配问题

7.3 高级图算法 #

• 拓扑排序
• 欧拉路径
• 哈密顿路径
• 平面图算法

八、字符串算法 #

8.1 模式匹配 #

• 朴素匹配算法
• KMP算法
• Boyer-Moore算法
• Rabin-Karp算法

8.2 字符串处理 #

• 字符串排序
• 字典树
• 后缀数组
• 后缀自动机

九、计算几何 #

9.1 基本概念 #

• 点、线、面表示
• 向量运算
• 几何变换
• 坐标系统

9.2 几何算法 #

• 凸包算法
• 线段相交检测
• 最近点对问题
• 多边形 triangulation

十、高级话题 #

10.1 近似算法 #

• 近似比分析
• 随机化算法
• 在线算法
• 并行算法

10.2 复杂度理论 #

• P与NP问题
• NP完全问题
• 归约技术
• 不可判定问题

10.3 实际应用 #

• 大数据处理
• 机器学习算法
• 网络算法
• 生物信息学算法