分治算法

分治框架

分治三步：Divide（将问题拆成独立子问题）→ Conquer（递归求解）→ Combine（合并子问题结果）。关键性质是子问题相互独立（与 DP 不同，DP 有重叠子问题）。

主定理（Master Theorem）

T(n) = aT(n/b) + f(n)，其中 a 个子问题，规模 n/b，合并代价 f(n)。三种情形：若 f(n) = O(n^log_b(a) / log^k n)，则 T(n) = Θ(n^log_b(a) * log^(k+1) n)（均摊情形）；工程中最常遇到的是 a=2,b=2,f(n)=O(n) → T(n)=O(n log n)（归并排序）。

常见算法复杂度

适用场景

• 问题可拆成规模相近的独立子问题
• 合并步骤是整个算法的核心逻辑
• 需要稳定排序（归并）或精确中位数（Quick Select 随机化）

主定理（Master Theorem）

主定理给出递推式 T(n) = a·T(n/b) + f(n) 的渐进解，其中 a ≥ 1、b > 1 为常数，f(n) 为合并代价。令 p = log_b(a)（子问题树叶节点数的指数）。

// Master Theorem: T(n) = a·T(n/b) + f(n),  p = log_b(a)
//
// Case 1 — leaves dominate:  f(n) = O(n^{p-ε})        →  T(n) = Θ(n^p)
// Case 2 — balanced:         f(n) = Θ(n^p · log^k n)  →  T(n) = Θ(n^p · log^{k+1} n)
// Case 3 — root dominates:   f(n) = Ω(n^{p+ε})        →  T(n) = Θ(f(n))
//
// Examples:
//   Merge Sort:   a=2, b=2, p=1, f=O(n)   → Case 2 → O(n log n)
//   Binary Search:a=1, b=2, p=0, f=O(1)   → Case 2 → O(log n)
//   Quick Select: a=1, b=2, p=0, f=O(n)   → Case 3 → O(n)  (expected)
//   Strassen:     a=7, b=2, p≈2.81,f=O(n²)→ Case 1 → O(n^{2.81})

三种情形

典型例子

记忆法：比较 f(n) 与 n^p 的关系：f 增长更慢（叶主导）→ Case 1；f 与 n^p 同量级（均衡）→ Case 2 加一个 log；f 增长更快（根主导）→ Case 3。

归并排序 & 逆序对

归并排序：拆成左右两半，递归排序，然后双指针合并两个有序子数组。稳定，O(n log n) 最坏，但需要 O(n) 额外空间。逆序对计数可在合并步骤中 O(1) 额外计算：右半的元素比左半当前元素小时，左半剩余元素个数即逆序对数。

// Merge Sort + count inversions
long long mergeCount(vector<int>& a, int l, int r) {
    if (r - l <= 1) return 0;
    int mid = (l + r) / 2;
    long long cnt = mergeCount(a, l, mid) + mergeCount(a, mid, r);
    vector<int> tmp;
    int i = l, j = mid;
    while (i < mid && j < r) {
        if (a[i] <= a[j]) tmp.push_back(a[i++]);
        else { cnt += mid - i; tmp.push_back(a[j++]); } // all a[i..mid) > a[j]
    }
    while (i < mid) tmp.push_back(a[i++]);
    while (j < r)   tmp.push_back(a[j++]);
    copy(tmp.begin(), tmp.end(), a.begin() + l);
    return cnt;
}

典型题目

• 912. 排序数组（归并实现）
• 315. 计算右侧小于当前元素的个数（逆序对变体）
• 493. 翻转对（自定义逆序对条件：nums[i] > 2*nums[j]）
• 23. 合并 K 个升序链表（K 路归并，见堆章节）

稳定性：归并排序是稳定排序（相等元素保持原有相对顺序），快速排序默认不稳定。若需稳定且 O(n log n)，选归并。

Quick Select

Quick Select 找第 k 小（大）元素。随机选 pivot，划分后只递归 pivot 所在的一侧，期望 O(n)，最坏 O(n²)（随机 pivot 可几乎消除最坏情形）。

算法步骤

1. 随机选 pivot，将数组划分为 [< pivot][pivot][> pivot]
2. 若 pivot 下标 == k，直接返回
3. 否则只递归 k 所在的一侧（不需要两侧都处理）

// Quick Select — kth smallest (0-indexed)
int quickSelect(vector<int>& nums, int l, int r, int k) {
    if (l == r) return nums[l];
    int pivot = nums[l + rand() % (r - l + 1)];
    int i = l, j = r;
    while (i <= j) {
        while (nums[i] < pivot) i++;
        while (nums[j] > pivot) j--;
        if (i <= j) swap(nums[i++], nums[j--]);
    }
    // after partition: nums[l..j] <= pivot <= nums[i..r]
    if (k <= j) return quickSelect(nums, l, j, k);
    if (k >= i) return quickSelect(nums, i, r, k);
    return pivot;
}

典型题目

• 215. 数组中的第 K 个最大元素（Quick Select 或堆）
• 347. 前 K 个高频元素（统计频次后 Quick Select）

vs 堆：Quick Select 期望 O(n)，适合只需一个 Kth 值且不需要前 K 个都有序的情形；堆 O(n log k) 且前 K 个可按顺序弹出。

Quick Select 随机化分析

不随机选 pivot 时，Quick Select 在有序或近似有序输入上退化为 O(n²)（每次 pivot 都是最小/最大元素，划分极不均衡）。随机化 pivot 使期望时间降至 O(n)。

为什么必须随机化

若固定选首元素为 pivot，对手可构造已排序输入使每次划分只去掉一个元素——递推变为 T(n) = T(n-1) + O(n) = O(n²)。随机 pivot 让划分结果与输入无关。

// LC 493 — Reverse Pairs: count pairs (i,j) where i<j and nums[i] > 2*nums[j]
// Key: count cross-pairs BEFORE merging (once left is sorted the two-pointer is O(n));
//      then merge normally to restore sorted order.
long long mergeRevPairs(vector<int>& a, int l, int r) {
    if (r - l <= 1) return 0;
    int mid = (l + r) / 2;
    long long cnt = mergeRevPairs(a, l, mid) + mergeRevPairs(a, mid, r);
    // count cross-pairs: for each j in [mid,r), find how many i in [l,mid) have a[i]>2*a[j]
    int k = mid;
    for (int j = mid; j < r; j++) {
        while (k < mid && (long long)a[k] <= 2LL * a[j]) k++;
        cnt += mid - k;
    }
    // standard merge
    inplace_merge(a.begin()+l, a.begin()+mid, a.begin()+r);
    return cnt;
}

期望复杂度直觉

随机 pivot 落在中间 50% 的概率为 1/2，此时两侧规模至多 3n/4。期望每 2 次尝试得到一次「好的」划分。由等比级数 n + 3n/4 + (3/4)²n + ... = 4n，得期望 T(n) = O(n)。

最坏 vs 期望：最坏仍为 O(n²)，但概率极低（对于随机 pivot，概率随 n 指数级趋近于 0）。工程中可接受。若需确定性 O(n)，使用 Median-of-Medians 算法，但常数更大。