[!info] related notes 算法面试题型 MOC 递归算法 排序算法总结

分治（Divide and Conquer）

分治的核心是：把一个”大问题”的答案拆成若干个”子问题”的答案，再把它们合并。

何时考虑分治

• 能把问题拆成左右两部分（或多部分），并且答案可以由子答案合并得到。
• 合并阶段可以被显著优化（例如利用”左右各自有序”的性质）。

一个常用的判断问法：

1. 大范围答案 = 左边答案 + 右边答案 + 跨越左右的答案吗？
2. 跨越左右的那部分，能不能利用”左/右有序”等结构做到更快？

典型结构

solve(l, r):
  if l == r: return base
  m = (l+r)/2
  left = solve(l, m)
  right = solve(m+1, r)
  cross = merge_or_count(l, m, r)
  return combine(left, right, cross)

典型例题

归并排序（Merge Sort）

拆分到单元素后，合并两个有序子数组。合并过程 $O(n)$，总复杂度 $O(n \log 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)

快速排序（Quick Sort）

选 pivot 分区，递归排序左右两部分。关键在 partition 的 $O(n)$ 操作。

二分查找（Binary Search）

每次排除一半搜索空间，本质是最简单的分治：只走一条分支，$O(\log n)$。

最近点对（Closest Pair of Points）

平面内 $n$ 个点找最近距离：按 x 坐标分治，合并时利用”条带内按 y 排序”将 $O(n^2)$ 降到 $O(n \log n)$。

常见题型

• 归并排序框架类统计：逆序对、小和、区间内满足某条件的对数。
• 在 merge 里做”跨区间贡献统计”。

例题：小和问题

• 小和问题

分治 vs 动态规划

维度	分治	动态规划
子问题关系	独立，互不重叠	重叠，共享子问题
子问题数量	通常 2 个	通常很多
是否需要缓存	不需要（子问题不重复）	需要（memo / table）
典型例子	归并排序、最近点对	背包、LCS、编辑距离

核心区别：如果子问题有重叠，用 DP；如果子问题独立，用分治。

主定理（Master Theorem）概览

对于递推 $T(n) = aT(n/b) + O(n^d)$：

条件	复杂度
$d < \log_b a$	$O(n^{\log_b a})$（递归主导）
$d = \log_b a$	$O(n^d \log n)$（均衡）
$d > \log_b a$	$O(n^d)$（合并主导）

例：归并排序 $T(n) = 2T(n/2) + O(n)$，$a=2, b=2, d=1$，$d = \log_2 2 = 1$，属于均衡情况，$O(n \log n)$。

最小提醒

• 分治本身不是目的；合并阶段能否做到线性/接近线性，决定是否值得。

相关笔记

• 递归算法
• 排序算法总结
• 算法面试题型 MOC