算法
→ 返回计算机基础
算法是解决问题的步骤序列。评价算法的核心指标是时间复杂度和空间复杂度。
复杂度
大 O 表示法
描述算法在最坏情况下随输入规模 n 增长的趋势，忽略常数项和低阶项：
| 复杂度 | 名称 | 示例 |
|---|---|---|
| O(1) | 常数 | 数组随机访问、哈希表查找 |
| O(log n) | 对数 | 二分查找、平衡树操作 |
| O(n) | 线性 | 线性扫描、链表遍历 |
| O(n log n) | 线性对数 | 归并排序、堆排序 |
| O(n²) | 平方 | 冒泡/插入排序、暴力匹配 |
| O(2ⁿ) | 指数 | 穷举子集、暴力递归 |
| O(n!) | 阶乘 | 全排列枚举 |
排序算法
比较排序
| 算法 | 时间（平均） | 时间（最坏） | 空间 | 稳定 |
|---|---|---|---|---|
| 冒泡排序 | O(n²) | O(n²) | O(1) | ✓ |
| 插入排序 | O(n²) | O(n²) | O(1) | ✓ |
| 选择排序 | O(n²) | O(n²) | O(1) | ✗ |
| 归并排序 | O(n log n) | O(n log n) | O(n) | ✓ |
| 快速排序 | O(n log n) | O(n²) | O(log n) | ✗ |
| 堆排序 | O(n log n) | O(n log n) | O(1) | ✗ |
快速排序：选基准值（pivot），将数组分为小于和大于 pivot 的两部分，递归排序。随机选 pivot 可避免最坏情况。
归并排序：分治，将数组对半分割，递归排序后合并两个有序子数组。
非比较排序（线性时间）
| 算法 | 时间 | 适用条件 |
|---|---|---|
| 计数排序 | O(n + k) | 整数，值域范围 k 不大 |
| 桶排序 | O(n + k) | 均匀分布的数据 |
| 基数排序 | O(d(n + k)) | 整数，d 为位数 |
查找算法
二分查找
在有序数组中查找目标值，每次将搜索范围减半：
left = 0, right = n-1
while left <= right:
mid = (left + right) / 2
if arr[mid] == target: return mid
elif arr[mid] < target: left = mid + 1
else: right = mid - 1
时间 O(log n)，空间 O(1)。变种：lower_bound/upper_bound 查找边界位置。
递归与分治
将问题分解为规模更小的同类子问题，递归求解后合并结果。
经典例子：归并排序、快速排序、二分查找、最大子数组（分治）。
递归优化：
- 记忆化（Memoization）：缓存已计算的子问题结果，避免重复计算
- 尾递归优化：将递归转化为迭代，避免栈溢出
动态规划（DP）
利用重叠子问题的最优解构造原问题的最优解（最优子结构）。
步骤：① 定义状态含义 → ② 写状态转移方程 → ③ 确定初始值和计算顺序
经典问题
0/1 背包：
dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])
最长公共子序列（LCS）：
dp[i][j] = dp[i-1][j-1] + 1 （s1[i] == s2[j]）
dp[i][j] = max(dp[i-1][j], dp[i][j-1]) （s1[i] != s2[j]）
最长递增子序列（LIS）：O(n²) DP 或 O(n log n) 二分优化。
编辑距离：插入、删除、替换三种操作的最小次数。
贪心算法
每步选择当前最优解，期望达到全局最优。需证明贪心选择性质和最优子结构。
| 问题 | 贪心策略 |
|---|---|
| 活动选择 | 优先选结束时间最早的活动 |
| 哈夫曼编码 | 优先合并权重最小的两个节点 |
| 最小生成树 | 每次选最小权边（Kruskal/Prim） |
| Dijkstra 最短路 | 每次松弛距离最近的未访问节点 |
图算法
最短路径
| 算法 | 适用 | 时间复杂度 |
|---|---|---|
| BFS | 无权图 | O(V+E) |
| Dijkstra | 非负权图 | O((V+E) log V)（堆优化） |
| Bellman-Ford | 含负权边 | O(VE) |
| Floyd-Warshall | 全对最短路 | O(V³) |
最小生成树
- Kruskal：按边权从小到大排序，用并查集判断是否成环，O(E log E)
- Prim：从任意节点出发，每次加入最近的未访问节点，O((V+E) log V)
拓扑排序
对有向无环图（DAG）线性排序：
- Kahn 算法：BFS + 入度表，O(V+E)
- DFS 后序：DFS 完成时入栈，最后逆序输出
回溯算法
枚举所有可能的解，遇到不满足约束的分支立即剪枝：
backtrack(state):
if 满足终止条件: 记录结果; return
for 每个候选选择:
做选择
backtrack(state)
撤销选择
经典问题：N 皇后、全排列、子集枚举、数独求解。
字符串算法
| 算法 | 用途 | 时间复杂度 |
|---|---|---|
| KMP | 字符串模式匹配 | O(n+m) |
| Rabin-Karp | 滚动哈希匹配 | O(n+m) 均摊 |
| Trie（前缀树） | 前缀查找、自动补全 | O(m) 查找 |