illegalCreed

中文

English

中文

English

Appearance

分治三步与主定理 ​

基于通用算法套路 · 核于 2026-07

速查 ​

  • 分治三步：分（Divide）——把原问题切成 a 个规模约 n/b 的同构子问题；治（Conquer）——递归求解子问题（足够小直接算）；合（Combine）——把子问题的解拼成原问题的解。
  • 递推关系：T(n) = a·T(n/b) + f(n)——a=子问题个数，n/b=子问题规模，f(n)=分解+合并代价。
  • 主定理（Master Theorem）：令 c = log_b(a)，比较 f(n) 与 n^c（即 n^(log_b a)）的大小，分三种情况：
    • 情况一（叶子主导）：f(n) = O(n^(c-ε))，则 T(n) = Θ(n^c)——递归树叶子太多，内部节点代价可忽略。
    • 情况二（平衡）：f(n) = Θ(n^c)，则 T(n) = Θ(n^c · log n)——各层代价相同，共 log n 层。
    • 情况三（根主导）：f(n) = Ω(n^(c+ε)) 且正则条件 a·f(n/b) ≤ k·f(n) (k<1)，则 T(n) = Θ(f(n))——根节点代价压倒一切。
  • 经典套用：归并 a=2,b=2,f=O(n)，c=1，情况二 → O(n log n)；二分 a=1,b=2,f=O(1)，c=0，情况二 → O(log n)；Strassen a=7,b=2,f=O(n²)，c=log₂7≈2.807，情况一 → O(n^2.807)。
  • 代码模板：solve(p) → 小则直接算 → subs=divide(p) → combine(subs.map(solve))。
  • 递归树直觉：共 log_b n 层，第 i 层有 a^i 个节点、每个代价 f(n/b^i)；总代价 = Σ aⁱ·f(n/bⁱ)。
  • 递归深度：每次除以 b → 深度 log_b n，栈空间 O(log n)；每次只减 1 → 深度 n，易栈溢出。
  • 正则条件：情况三要求 a·f(n/b) ≤ k·f(n)（k<1），即「每层代价单调下降」——保证根节点真的主导，否则不适用。
  • 进阶：主定理之外还有 Akra-Bazzi 公式（处理子问题规模不均的情况，如 T(n)=T(n/3)+T(2n/3)+O(n)）。

一、分治三步详解 ​

分治的核心是三步「分—治—合」。以归并排序为例：

排序 [38,27,43,3,9,82,10]    （原问题规模 n=7）

①分 Divide：从中间切成两半（代价 O(1)）
   左 [38,27,43,3]    右 [9,82,10]    （各约 n/2）

②治 Conquer：递归排序两半
   左 [3,27,38,43]    右 [9,10,82]    （子问题已解）

③合 Combine：双指针归并两个有序序列（代价 O(n)）
   [3,9,10,27,38,43,82]    ← 原问题解

三个动作里，「合」往往是复杂度的决定因素：

  • 归并的「合」是 O(n)（线性扫描两个有序序列）→ 总 O(n log n)。
  • 快排的「合」是 O(1)（partition 已经就位，无需显式合并）→ 总 O(n log n)。
  • Strassen 的「合」是若干矩阵加减 O(n²) → 总 O(n^2.807)。

代码模板 ​

js
function solve(problem) {
  if (isSmallEnough(problem)) return solveDirectly(problem); // 边界
  const subs = divide(problem);        // ① 分
  const results = subs.map(solve);     // ② 治（递归）
  return combine(results);             // ③ 合
}

二、递推关系 T(n)=aT(n/b)+f(n) ​

任何分治算法的复杂度都可写成这个形式：

T(n) = a · T(n/b) + f(n)
         │       │      │
         │       │      └─ 分解 + 合并的总代价
         │       └────── 每个子问题的规模是原问题的 1/b
         └────────────── 每次切成 a 个子问题

参数读法：

算法a（子问题数）b（规模缩减）f(n)（分合代价）含义
二分查找12O(1)只保留一半，比较 O(1)
归并排序22O(n)两半各排，归并 O(n)
快速排序（平均）22O(n)partition 后两半，划分 O(n)
Karatsuba32O(n)3 个子乘法，加减 O(n)
Strassen72O(n²)7 个子矩阵乘，加减 O(n²)

三、主定理：三种情况 ​

主定理（Master Theorem）给出 T(n)=aT(n/b)+f(n) 的闭式解。令 临界函数 g(n) = n^(log_b a)（即 n^c，其中 c = log_b a），比较 f(n) 与 g(n) 的大小关系：

            代价
             │
   f(n) ─── 在此之上（情况三，根主导）
             │        T(n) = Θ(f(n))
   ─────────┼──────── g(n) = n^c    （临界线）
             │        T(n) = Θ(n^c · log n)   （情况二，平衡）
   f(n) ─── 在此之下（情况一，叶子主导）
             │        T(n) = Θ(n^c) = Θ(n^(log_b a))
             └──────── n 规模

情况一：叶子主导（f(n) 多项式小于 n^c） ​

若 f(n) = O(n^(c-ε)) 对某个 ε>0 成立（即 f(n) 比 n^c 至少慢一个多项式因子），则：

T(n) = Θ(n^c) = Θ(n^(log_b a))

直觉：递归树的叶子节点（共 a^(log_b n) = n^c 个）数量太多，它们的总代价压倒了内部节点的 f(n) 之和。

例子：Strassen 矩阵乘法 a=7, b=2, f(n)=O(n²)。c = log₂7 ≈ 2.807，f(n)=O(n²) = O(n^(2.807-0.8))，满足情况一 → T(n)=Θ(n^2.807)。

情况二：平衡（f(n) 与 n^c 同阶） ​

若 f(n) = Θ(n^c)（或更一般地 f(n) = Θ(n^c · log^k n)），则：

T(n) = Θ(n^c · log n)            （k=0 时）
T(n) = Θ(n^c · log^(k+1) n)      （一般情况）

直觉：递归树每层代价相同（都是 Θ(n^c)），共 log_b n 层，总代价相乘。

例子：

  • 归并排序 a=2,b=2,f(n)=O(n)，c=log₂2=1，f(n)=Θ(n¹) → 情况二 → T(n)=Θ(n log n)。
  • 二分查找 a=1,b=2,f(n)=O(1)，c=log₂1=0，f(n)=Θ(n⁰)=Θ(1) → 情况二 → T(n)=Θ(log n)。

情况三：根主导（f(n) 多项式大于 n^c） ​

若 f(n) = Ω(n^(c+ε)) 对某个 ε>0 成立，且满足正则条件 a·f(n/b) ≤ k·f(n)（k<1，即每层代价严格递减），则：

T(n) = Θ(f(n))

直觉：根节点的代价 f(n) 太大，压倒了所有子节点代价之和（正则条件保证子节点代价收敛）。

例子：某分治 a=2, b=2, f(n)=O(n³)。c=1，f(n)=Ω(n^(1+2))，正则条件 2·f(n/2)=2·(n/2)³=n³/4 ≤ (3/4)·n³ 满足（k=3/4<1）→ 情况三 → T(n)=Θ(n³)。

三种情况速记表 ​

情况条件结论谁主导
一f(n) = O(n^(c-ε))T(n) = Θ(n^c)叶子（递归终点）
二f(n) = Θ(n^c · log^k n)T(n) = Θ(n^c · log^(k+1) n)平衡（各层相当）
三f(n) = Ω(n^(c+ε)) 且正则T(n) = Θ(f(n))根（分解合并）

其中 c = log_b a。三种情况之外（如 f(n) 与 n^c 既不多项式大也不多项式小）主定理不适用，需画递归树或用 Akra-Bazzi 公式。

四、用主定理分析经典算法 ​

归并排序：T(n)=2T(n/2)+O(n) ​

a=2, b=2, f(n)=O(n)。c = log₂2 = 1，f(n)=Θ(n¹)=Θ(n^c) → 情况二 → T(n)=Θ(n log n)。

二分查找：T(n)=T(n/2)+O(1) ​

a=1, b=2, f(n)=O(1)。c = log₂1 = 0，f(n)=Θ(n⁰)=Θ(1)=Θ(n^c) → 情况二 → T(n)=Θ(log n)。

注意二分是 a=1（只保留一半），所以是减治而非典型分治，主定理情况二照样适用。

快速排序（平均）：T(n)=2T(n/2)+O(n) ​

平均情况下 partition 大致对半，a=2, b=2, f(n)=O(n)，与归并相同 → 平均 O(n log n)。

最坏情况（已有序 + 取端点为 pivot）：partition 退化成 1 和 n-1，T(n)=T(n-1)+O(n)=O(n²)——主定理不适用（子问题规模不均），需用递归树或直接求和。

Strassen 矩阵乘法：T(n)=7T(n/2)+O(n²) ​

a=7, b=2, f(n)=O(n²)。c = log₂7 ≈ 2.807，f(n)=O(n²)=O(n^(2.807-0.8)) → 情况一 → T(n)=Θ(n^2.807)。这正是 Strassen 优于朴素 O(n³) 的根源。

Karatsuba 大整数乘法：T(n)=3T(n/2)+O(n) ​

a=3, b=2, f(n)=O(n)。c = log₂3 ≈ 1.585，f(n)=O(n)=O(n^(1.585-0.585)) → 情况一 → T(n)=Θ(n^1.585)，优于朴素 O(n²)。

五、递归树：主定理的直觉来源 ​

主定理的三种情况都能从递归树直观理解：

                  根（代价 f(n)）
                 /              \
            f(n/b)              f(n/b)        第 1 层：a 个节点，每个代价 f(n/b)
           /    \              /    \
       f(n/b²) f(n/b²)    f(n/b²) f(n/b²)    第 2 层：a² 个，每个 f(n/b²)
            ...                              （共 log_b n 层）
        叶子：a^(log_b n) = n^c 个，每个 O(1)
  • 每层代价：第 i 层有 aⁱ 个节点，每个代价 f(n/bⁱ)，层代价 = aⁱ · f(n/bⁱ)。
  • 总代价：Σ（i=0 到 log_b n）aⁱ · f(n/bⁱ)。
  • 三种情况就是看这个求和被「叶子层」还是「根层」还是「各层平均」主导。

六、分治代码模板（归并排序实例） ​

js
function mergeSort(a) {
  if (a.length <= 1) return a;                 // 边界
  const mid = a.length >> 1;                    // ① 分
  const left = mergeSort(a.slice(0, mid));      // ② 治（左）
  const right = mergeSort(a.slice(mid));        // ② 治（右）
  return merge(left, right);                    // ③ 合
}
function merge(a, b) {
  const res = []; let i = 0, j = 0;
  while (i < a.length && j < b.length)
    a[i] <= b[j] ? res.push(a[i++]) : res.push(b[j++]);
  while (i < a.length) res.push(a[i++]);
  while (j < b.length) res.push(b[j++]);
  return res;
}

mergeSort 即模板的具象：isSmallEnough = 长度 ≤1；divide = 从中间切两半；combine = merge。merge 的 O(n) 代价决定了 f(n)=O(n)，配合 a=b=2 得 O(n log n)。

下一步 ​

掌握了主定理后，下一步是看分治在经典问题上的具体应用——归并/快排、二分、最近点对、Karatsuba、Strassen，见经典分治应用。