算法课高频考点完全指南
算法课（通常叫 Algorithm Design、Algorithms、Introduction to Algorithms）是 CS 本科和研究生最重要的必修课之一，也是大厂 Coding Interview 的直接考核内容。
但很多学生在算法课上的困境是：看懂了，写不出来；能写出来，但 Big-O 分析不对；Big-O 能算，但 Dynamic Programming 的 Recurrence 写不出来。
这篇指南聚焦四个最高频考点，给出可以直接用的框架。
一、Big-O 复杂度分析
Big-O 分析是算法课每道题的必答部分，分析错误会失去 10–30% 的分数。
常见复杂度排序（从快到慢）
O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!)
递归复杂度的 Master Theorem
对于 T(n) = aT(n/b) + f(n) 形式的递归：
| 条件 | 结论 |
|---|---|
| f(n) = O(n^(log_b(a) - ε)) | T(n) = Θ(n^log_b(a)) |
| f(n) = Θ(n^log_b(a)) | T(n) = Θ(n^log_b(a) · log n) |
| f(n) = Ω(n^(log_b(a) + ε)) | T(n) = Θ(f(n)) |
常用记忆：
- 归并排序：
T(n) = 2T(n/2) + O(n)→ O(n log n) - 二分搜索：
T(n) = T(n/2) + O(1)→ O(log n) - 快速排序平均：
T(n) = 2T(n/2) + O(n)→ O(n log n)（但最坏 O(n²)）
易错点
循环嵌套不一定是 O(n²)：
# 这是 O(n) 而不是 O(n²)！
i = 0
while i < n:
j = i
while j < n:
j *= 2 # j 每次翻倍，内层是 O(log n)
i += 1
# 外层 O(n)，内层 O(log n)，总体 O(n log n)
空间复杂度别忘了递归栈：
- DFS 递归的递归栈深度 = O(树的深度) = O(log n)（平衡树）或 O(n)（退化链表）
二、排序算法
各排序算法对比
| 算法 | 时间（平均） | 时间（最坏） | 空间 | 稳定 |
|---|---|---|---|---|
| Bubble Sort | O(n²) | O(n²) | O(1) | ✓ |
| Selection Sort | O(n²) | O(n²) | O(1) | ✗ |
| Insertion Sort | O(n²) | O(n²) | O(1) | ✓ |
| Merge Sort | O(n log n) | O(n log n) | O(n) | ✓ |
| Quick Sort | O(n log n) | O(n²) | O(log n) | ✗ |
| Heap Sort | O(n log n) | O(n log n) | O(1) | ✗ |
| Counting Sort | O(n + k) | O(n + k) | O(k) | ✓ |
考试常考的问题：
- 为什么 Quick Sort 最坏 O(n²)？（每次 pivot 选到最大/最小值，退化为 n 层递归）
- 为什么 Merge Sort 总是 O(n log n)？（每次确定性二分，不依赖数据分布）
- 什么情况下 Insertion Sort 是 O(n)？（输入已经有序时，每次只比较一次）
归并排序代码框架
def merge_sort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = merge_sort(arr[:mid])
right = merge_sort(arr[mid:])
return merge(left, right)
def merge(left, right):
result = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
result.append(left[i]); i += 1
else:
result.append(right[j]); j += 1
result.extend(left[i:])
result.extend(right[j:])
return result
三、动态规划（Dynamic Programming）
动态规划是算法课最难的部分，也是期末考试分值最高的题型（通常占 30–40%）。
DP 解题四步框架
- 定义状态（State Definition）：
dp[i]或dp[i][j]代表什么？ - 写出转移方程（Recurrence）：
dp[i]如何从前面的状态推导？ - 确定初始值（Base Cases）：
dp[0]或dp[i][0]等边界值 - 确定计算顺序（Iteration Order）：从哪个方向填表？
经典 DP 问题
1. 最长上升子序列（LIS - Longest Increasing Subsequence）
def length_of_lis(nums):
n = len(nums)
dp = [1] * n # dp[i] = 以 nums[i] 结尾的 LIS 长度
for i in range(1, n):
for j in range(i):
if nums[j] < nums[i]:
dp[i] = max(dp[i], dp[j] + 1)
return max(dp)
# 时间 O(n²)，可优化到 O(n log n)
2. 0/1 背包问题（0/1 Knapsack）
def knapsack(weights, values, capacity):
n = len(weights)
# dp[i][w] = 前 i 件物品在容量 w 下的最大价值
dp = [[0] * (capacity + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
for w in range(capacity + 1):
# 不选第 i 件：dp[i-1][w]
dp[i][w] = dp[i-1][w]
# 选第 i 件（如果放得下）
if weights[i-1] <= w:
dp[i][w] = max(dp[i][w], dp[i-1][w-weights[i-1]] + values[i-1])
return dp[n][capacity]
3. 最长公共子序列（LCS - Longest Common Subsequence）
def lcs(s1, s2):
m, n = len(s1), len(s2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
if s1[i-1] == s2[j-1]:
dp[i][j] = dp[i-1][j-1] + 1
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
return dp[m][n]
4. 硬币找零（Coin Change）
def coin_change(coins, amount):
dp = [float('inf')] * (amount + 1)
dp[0] = 0
for i in range(1, amount + 1):
for coin in coins:
if coin <= i:
dp[i] = min(dp[i], dp[i - coin] + 1)
return dp[amount] if dp[amount] != float('inf') else -1
DP 考试失分点
- 状态定义不清楚：写 Recurrence 之前必须先明确
dp[i]的含义，否则转移方程无法成立 - Base Case 漏掉：所有 DP 题必须明确边界初始值
- 迭代顺序搞反：有些 DP 需要从右到左填表（滚动数组优化时特别注意）
- 只给 Recurrence，不给最终答案：
dp[n]不一定是答案，LIS 的答案是max(dp)
四、回溯法（Backtracking）
回溯法适用于：排列组合、子集、数独、N 皇后等穷举问题。
回溯代码模板
def backtrack(path, choices, result):
# 终止条件（Base Case）
if 满足终止条件:
result.append(path[:]) # 注意要拷贝！
return
for choice in choices:
# 做选择
path.append(choice)
# 递归
backtrack(path, updated_choices, result)
# 撤销选择（回溯）
path.pop()
经典回溯题
全排列（Permutations）：
def permute(nums):
result = []
def backtrack(path, remaining):
if not remaining:
result.append(path[:])
return
for i, num in enumerate(remaining):
path.append(num)
backtrack(path, remaining[:i] + remaining[i+1:])
path.pop()
backtrack([], nums)
return result
子集（Subsets）：
def subsets(nums):
result = []
def backtrack(start, path):
result.append(path[:])
for i in range(start, len(nums)):
path.append(nums[i])
backtrack(i + 1, path)
path.pop()
backtrack(0, [])
return result
考试最后 1 周的复习清单
- 能默写归并排序并分析 O(n log n)
- 能用 Master Theorem 分析递归 T(n)
- 能写 BFS/DFS 模板（图和树两种）
- 能用四步框架分析任意 DP 题
- 能写 0/1 背包、LCS、LIS 代码
- 能用回溯模板解决排列/子集问题
- 了解 NP-Hard / NP-Complete 的基本概念（理论课考点）
如果算法课让你感到力不从心，欢迎联系我们的 CS 辅导团队——无论是 Problem Set 卡住了还是期末考前需要系统梳理，我们都能提供针对性支持。
相关院校算法课辅导： UIUC CS 374 · UCLA CS 180 · Columbia COMS 4231 · UToronto CSC373 · UNSW COMP3121
