算法¶
算法（Algorithm）是一组被精确定义、计算机可执行的有限步骤，接受输入并在有限时间与空间内产生有效输出。算法中的每条指令都必须无歧义，执行过程从确定的初始状态出发，经过一系列状态转移最终到达终态并停止。状态之间的转移不一定是确定性的——包括随机化算法在内，部分算法会引入随机输入以获得更优的平均性能。
评价一个算法通常从两个维度入手：时间复杂度（执行步骤随输入规模的增长趋势）和空间复杂度（所需额外内存随输入规模的增长趋势），二者共同决定了算法在实际场景中的适用性。
本章涵盖的常用算法类型如下：
| 算法 | 核心思想 | 典型场景 |
|---|---|---|
| 递归 | 将问题拆解为同类子问题，通过函数自我调用求解 | 树的遍历、数学归纳 |
| 动规 | 记录子问题结果，避免重复计算，自底向上或自顶向下构建最优解 | 最长公共子序列、背包问题 |
| 贪心 | 每步选取局部最优，期望累积得到全局最优 | 区间调度、最小生成树 |
| 回溯 | 深度优先枚举所有可能，遇到不满足条件时剪枝回退 | 全排列、N 皇后、组合搜索 |
| 排序 | 将序列按指定规则重新排列，是众多算法的基础预处理步骤 | 归并排序、快速排序 |
| 遍历 | 系统地访问图或树中的每个节点，分为 BFS（广度优先）和 DFS（深度优先）两类 | 最短路径、连通性检测 |