什么是分治范式（divide-and-conquer paradigm）？

Question

Accepted Answer

**Divide and conquer** 通过 (1) 将问题**分解**为较小的子问题，(2) **递归地**求解每个子问题，以及 (3) **合并**结果来解决问题。许多高效算法都遵循这个模板。

## 核心思想

如果子问题是独立的且规模快速缩小，那么总工作量遵循可以用 **Master Theorem** 分析的递推关系。

## 例子：通过分治求最大元素

```python
def max_dc(arr, lo, hi):
    if lo == hi:                       # base case: one element
        return arr[lo]
    mid = (lo + hi) // 2
    left = max_dc(arr, lo, mid)        # conquer left
    right = max_dc(arr, mid + 1, hi)   # conquer right
    return max(left, right)            # combine

max_dc([3, 9, 2, 7], 0, 3)            # -> 9
```

## 经典例子

- **Merge sort / quicksort** — O(n log n) 排序。
- **Binary search** — O(log n)。
- **Fast exponentiation, Karatsuba multiplication, closest pair。**

## 复杂度

通常 T(n) = a·T(n/b) + f(n)；对于 merge sort，T(n) = 2T(n/2) + O(n) = **O(n log n)**。

## 何时使用 / 常见陷阱

当问题能**清晰地**分解为独立的子问题时使用。如果子问题**存在重叠**，应优先选择动态规划（以避免重复计算）。递归开销和合并步骤可能对小输入造成主导影响。

## 为什么这很重要

Divide and conquer 是大量高效算法背后的可重用蓝图。

识别这个模式让你能够通过递推关系快速推导和分析新算法。

它也自然地映射到并行计算中，因为独立的子问题可以并发运行。