为什么把问题拆开反而更快？分治算法从主定理到LeetCode完整指南

假设要在一百万个有序数字中找到某个特定值，最直接的想法是从头到尾逐个检查——运气好第一个就是，运气不好要找一百万次。但如果每次都将搜索范围缩小一半，最多只需要20次就能确定结果。这种"分而治之"的智慧，不仅让二分查找成为效率典范，更催生了归并排序、快速选择、Strassen矩阵乘法等一系列经典算法。

分治算法（Divide and Conquer）的核心思想极其朴素：将复杂问题拆分成若干个规模较小的相同问题，递归地求解这些子问题，最后将子问题的解合并得到原问题的解。这个看似简单的策略，却隐藏着深刻的数学原理——为什么把问题拆开反而更快？答案就藏在递归树的结构和主定理的证明中。

分治的几何直观：递归树上的代价分配

理解分治算法效率的关键，在于理解递归树的结构。考虑一个将规模为 $n$ 的问题分解成 $a$ 个规模为 $n/b$ 的子问题的算法：

graph TD
    A["问题规模 n<br/>代价 f(n)"] --> B["子问题 n/b"]
    A --> C["子问题 n/b"]
    A --> D["..."]
    
    B --> E["子问题 n/b²"]
    B --> F["子问题 n/b²"]
    B --> G["..."]
    
    C --> H["子问题 n/b²"]
    C --> I["子问题 n/b²"]
    C --> J["..."]
    
    style A fill:#e1f5fe
    style B fill:#fff3e0
    style C fill:#fff3e0
    style E fill:#e8f5e9
    style F fill:#e8f5e9
    style H fill:#e8f5e9
    style I fill:#e8f5e9

递归树的每个节点代表一次函数调用，节点中记录的工作量是该次调用中"非递归部分"的代价。树的叶子是基准情况，不产生新的递归调用。整棵树的总工作量就是算法的时间复杂度。

关键观察是：递归树的叶子节点数量取决于分解的"速度"。当 $a > 1$ 时（产生多个子问题），树的宽度会逐层扩展；当 $b > 1$ 时（子问题规模缩小），树的高度会受限于 $\log_b n$。

这两种力量的博弈，决定了算法的效率。这正是主定理要解决的问题：如何根据分解参数 $a$、$b$ 和合并代价 $f(n)$，快速判断算法的时间复杂度。

主定理：分治算法的复杂度速查表

主定理（Master Theorem）最早由 Jon Bentley、Dorothea Haken 和 James B. Saxe 在 1980 年提出，后来被《算法导论》推广普及。它为形如 $T(n) = aT(n/b) + f(n)$ 的递推式提供了统一的求解框架。

其中：

$a \geq 1$ 是子问题的数量
$b > 1$ 是子问题规模缩小的因子
$f(n)$ 是分解问题和合并解的代价

主定理的核心是比较 $f(n)$ 与临界函数 $n^{\log_b a}$ 的大小关系。临界函数代表了递归树叶节点数量增长的速度——当子问题数量 $a$ 较大时，叶子节点数量增长快，临界函数增长也快。

三种情况

情况一：叶节点主导。当 $f(n) = O(n^c)$ 且 $c < \log_b a$ 时，递归树的叶节点数量增长快于单节点的工作量增长，总代价由叶节点决定：

$$T(n) = \Theta(n^{\log_b a})$$

情况二：各层均衡。当 $f(n) = \Theta(n^{\log_b a} \cdot \log^k n)$ 时，分解合并代价与叶节点数量增长相当，每一层的代价相近：

$$T(n) = \Theta(n^{\log_b a} \cdot \log^{k+1} n)$$

情况三：根节点主导。当 $f(n) = \Omega(n^c)$ 且 $c > \log_b a$，同时满足正则条件 $af(n/b) \leq kf(n)$（$k < 1$）时，根节点的工作量远超叶节点：

$$T(n) = \Theta(f(n))$$

经典算法的主定理分析

算法	递推式	参数	情况	复杂度
二分查找	$T(n) = T(n/2) + O(1)$	$a=1, b=2, f(n)=1$	情况二	$O(\log n)$
归并排序	$T(n) = 2T(n/2) + O(n)$	$a=2, b=2, f(n)=n$	情况二	$O(n\log n)$
二叉树遍历	$T(n) = 2T(n/2) + O(1)$	$a=2, b=2, f(n)=1$	情况一	$O(n)$

归并排序是主定理应用的经典案例。$a=2$ 表示每次分解成两个子问题，$b=2$ 表示每个子问题规模减半，$f(n)=n$ 表示合并两个有序数组的代价。$\log_2 2 = 1$，而 $f(n) = n = n^{\log_b a}$，属于情况二中 $k=0$ 的特例，因此 $T(n) = \Theta(n \log n)$。

分治算法的历史突破

分治策略的应用催生了多个计算机科学史上的里程碑。1960年，23岁的俄罗斯数学家 Anatolii Karatsuba 发现了一种快速乘法算法，推翻了 Andrey Kolmogorov 关于 $n^2$ 次操作是乘法下界的猜想。

传统乘法需要 $n^2$ 次一位数乘法。Karatsuba 的洞察是：将两个 $n$ 位数分别拆成高位和低位两部分，即 $x = a \cdot 10^{n/2} + b$，$y = c \cdot 10^{n/2} + d$。那么：

$$xy = ac \cdot 10^n + (ad + bc) \cdot 10^{n/2} + bd$$

表面上看需要计算四次乘法：$ac$、$ad$、$bc$、$bd$。但 Karatsuba 发现 $(a+b)(c+d) = ac + ad + bc + bd$，因此 $ad + bc = (a+b)(c+d) - ac - bd$，只需三次乘法。这给出了递推式 $T(n) = 3T(n/2) + O(n)$，复杂度为 $O(n^{\log_2 3}) \approx O(n^{1.585})$。

1969年，Volker Strassen 将类似思想应用于矩阵乘法，将 $2 \times 2$ 矩阵乘法从 8 次乘法降到 7 次，实现了 $O(n^{\log_2 7}) \approx O(n^{2.807})$ 的复杂度。

这些算法共同揭示了一个深刻的事实：算法的效率不仅取决于问题本身，更取决于解决问题的策略。

LeetCode 分治题目分类与详解

分治算法在 LeetCode 上有广泛的应用，根据题目特点可以分成以下几类：

类型一：排序与选择

148. 排序链表

题目：给定链表的头节点，返回排序后的链表。要求 $O(n \log n)$ 时间复杂度和常数级空间复杂度。

分析：链表不支持随机访问，快速排序难以高效实现。归并排序的分治特性恰好适合链表：找到中点、递归排序两个子链表、合并有序链表。

Java 实现：

class Solution {
    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        
        // 使用快慢指针找到中点
        ListNode slow = head, fast = head.next;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        
        // 断开链表
        ListNode mid = slow.next;
        slow.next = null;
        
        // 递归排序
        ListNode left = sortList(head);
        ListNode right = sortList(mid);
        
        // 合并有序链表
        return merge(left, right);
    }
    
    private ListNode merge(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
        ListNode curr = dummy;
        
        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                curr.next = l1;
                l1 = l1.next;
            } else {
                curr.next = l2;
                l2 = l2.next;
            }
            curr = curr.next;
        }
        
        curr.next = (l1 != null) ? l1 : l2;
        return dummy.next;
    }
}

复杂度分析：$T(n) = 2T(n/2) + O(n)$，由主定理得 $O(n \log n)$。

215. 数组中的第K个最大元素

题目：找到未排序数组中第 $k$ 大的元素。

分析：快速选择算法是快速排序的变种。选择一个基准元素进行分区，若基准正好在第 $k$ 个位置则返回，否则只递归处理包含第 $k$ 个元素的那一侧。平均复杂度 $O(n)$，最坏 $O(n^2)$。

Java 实现：

class Solution {
    public int findKthLargest(int[] nums, int k) {
        // 第 k 大等价于第 (n-k+1) 小
        return quickSelect(nums, 0, nums.length - 1, nums.length - k);
    }
    
    private int quickSelect(int[] nums, int left, int right, int k) {
        if (left == right) {
            return nums[left];
        }
        
        // 分区
        int pivotIndex = partition(nums, left, right);
        
        if (pivotIndex == k) {
            return nums[pivotIndex];
        } else if (pivotIndex < k) {
            return quickSelect(nums, pivotIndex + 1, right, k);
        } else {
            return quickSelect(nums, left, pivotIndex - 1, k);
        }
    }
    
    private int partition(int[] nums, int left, int right) {
        int pivot = nums[right];
        int i = left;
        
        for (int j = left; j < right; j++) {
            if (nums[j] <= pivot) {
                swap(nums, i, j);
                i++;
            }
        }
        swap(nums, i, right);
        return i;
    }
    
    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

类型二：区间问题

53. 最大子数组和

题目：找到具有最大和的连续子数组。

分析：分治解法将数组分成左右两半，最大子数组和要么完全在左半部分，要么完全在右半部分，要么跨越中点。跨越中点的情况可以在线性时间内计算。

Java 实现：

class Solution {
    public int maxSubArray(int[] nums) {
        return divide(nums, 0, nums.length - 1);
    }
    
    private int divide(int[] nums, int left, int right) {
        if (left == right) {
            return nums[left];
        }
        
        int mid = left + (right - left) / 2;
        
        // 三种情况取最大值
        int leftMax = divide(nums, left, mid);
        int rightMax = divide(nums, mid + 1, right);
        int crossMax = crossSum(nums, left, right, mid);
        
        return Math.max(Math.max(leftMax, rightMax), crossMax);
    }
    
    private int crossSum(int[] nums, int left, int right, int mid) {
        // 从中点向左扫描的最大和
        int leftSum = Integer.MIN_VALUE;
        int sum = 0;
        for (int i = mid; i >= left; i--) {
            sum += nums[i];
            leftSum = Math.max(leftSum, sum);
        }
        
        // 从中点向右扫描的最大和
        int rightSum = Integer.MIN_VALUE;
        sum = 0;
        for (int i = mid + 1; i <= right; i++) {
            sum += nums[i];
            rightSum = Math.max(rightSum, sum);
        }
        
        return leftSum + rightSum;
    }
}

复杂度分析：$T(n) = 2T(n/2) + O(n)$，复杂度 $O(n \log n)$。虽然不如 Kadane 算法的 $O(n)$ 优，但分治解法展示了问题的结构特性。

315. 计算右侧小于当前元素的个数

题目：对于数组中每个元素，计算其右侧比它小的元素个数。

分析：这是归并排序的衍生问题。在归并过程中，当右半部分的元素被选中时，说明左半部分剩余的元素都比它大，可以统计逆序对。

Java 实现：

class Solution {
    private int[] counts;
    private int[] indexes;
    
    public List<Integer> countSmaller(int[] nums) {
        int n = nums.length;
        counts = new int[n];
        indexes = new int[n];
        
        for (int i = 0; i < n; i++) {
            indexes[i] = i;
        }
        
        mergeSort(nums, 0, n - 1);
        
        List<Integer> result = new ArrayList<>();
        for (int count : counts) {
            result.add(count);
        }
        return result;
    }
    
    private void mergeSort(int[] nums, int left, int right) {
        if (left >= right) return;
        
        int mid = left + (right - left) / 2;
        mergeSort(nums, left, mid);
        mergeSort(nums, mid + 1, right);
        merge(nums, left, mid, right);
    }
    
    private void merge(int[] nums, int left, int mid, int right) {
        int[] tempIndexes = new int[right - left + 1];
        int i = left, j = mid + 1, k = 0;
        int rightCount = 0;
        
        while (i <= mid && j <= right) {
            if (nums[indexes[j]] < nums[indexes[i]]) {
                rightCount++;
                tempIndexes[k++] = indexes[j++];
            } else {
                counts[indexes[i]] += rightCount;
                tempIndexes[k++] = indexes[i++];
            }
        }
        
        while (i <= mid) {
            counts[indexes[i]] += rightCount;
            tempIndexes[k++] = indexes[i++];
        }
        
        while (j <= right) {
            tempIndexes[k++] = indexes[j++];
        }
        
        for (int m = 0; m < tempIndexes.length; m++) {
            indexes[left + m] = tempIndexes[m];
        }
    }
}

类型三：表达式与构造

241. 为运算表达式设计优先级

题目：给定包含数字和运算符的表达式，通过添加括号改变运算顺序，计算所有可能的结果。

分析：对于表达式中的每个运算符，都可以作为最后一步运算。将表达式分成左右两部分，递归计算所有可能的结果，再根据运算符组合。

Java 实现：

class Solution {
    public List<Integer> diffWaysToCompute(String expression) {
        List<Integer> result = new ArrayList<>();
        
        for (int i = 0; i < expression.length(); i++) {
            char c = expression.charAt(i);
            
            if (c == '+' || c == '-' || c == '*') {
                // 分治：以当前运算符为分割点
                List<Integer> left = diffWaysToCompute(expression.substring(0, i));
                List<Integer> right = diffWaysToCompute(expression.substring(i + 1));
                
                // 合并结果
                for (int l : left) {
                    for (int r : right) {
                        switch (c) {
                            case '+': result.add(l + r); break;
                            case '-': result.add(l - r); break;
                            case '*': result.add(l * r); break;
                        }
                    }
                }
            }
        }
        
        // 基准情况：纯数字
        if (result.isEmpty()) {
            result.add(Integer.parseInt(expression));
        }
        
        return result;
    }
}

932. 漂亮数组

题目：构造数组使得对于任意 $i < k < j$，都有 $2 \cdot nums[k] \neq nums[i] + nums[j]$。

分析：关键观察是如果奇数放左边、偶数放右边，则 $nums[i] + nums[j]$ 必为奇数，而 $2 \cdot nums[k]$ 必为偶数，永远不会相等。对奇数部分和偶数部分分别递归构造。

Java 实现：

class Solution {
    private Map<Integer, int[]> memo = new HashMap<>();
    
    public int[] beautifulArray(int n) {
        return construct(n);
    }
    
    private int[] construct(int n) {
        if (memo.containsKey(n)) {
            return memo.get(n);
        }
        
        int[] result = new int[n];
        if (n == 1) {
            result[0] = 1;
        } else {
            int t = 0;
            // 奇数部分：(x-1)*2+1
            int[] left = construct((n + 1) / 2);
            for (int x : left) {
                result[t++] = x * 2 - 1;
            }
            
            // 偶数部分：x*2
            int[] right = construct(n / 2);
            for (int x : right) {
                result[t++] = x * 2;
            }
        }
        
        memo.put(n, result);
        return result;
    }
}

类型四：几何与最近邻

973. 最接近原点的 K 个点

题目：找到平面上距离原点最近的 $k$ 个点。

分析：可以转换为寻找第 $k$ 小的距离值，使用快速选择算法。距离相等的点可以任意顺序返回。

Java 实现：

class Solution {
    public int[][] kClosest(int[][] points, int k) {
        quickSelect(points, 0, points.length - 1, k);
        
        int[][] result = new int[k][2];
        for (int i = 0; i < k; i++) {
            result[i] = points[i];
        }
        return result;
    }
    
    private void quickSelect(int[][] points, int left, int right, int k) {
        if (left >= right) return;
        
        int pivotIndex = partition(points, left, right);
        
        if (pivotIndex == k - 1) {
            return;
        } else if (pivotIndex < k - 1) {
            quickSelect(points, pivotIndex + 1, right, k);
        } else {
            quickSelect(points, left, pivotIndex - 1, k);
        }
    }
    
    private int partition(int[][] points, int left, int right) {
        int pivotDist = dist(points[right]);
        int i = left;
        
        for (int j = left; j < right; j++) {
            if (dist(points[j]) <= pivotDist) {
                swap(points, i, j);
                i++;
            }
        }
        swap(points, i, right);
        return i;
    }
    
    private int dist(int[] point) {
        return point[0] * point[0] + point[1] * point[1];
    }
    
    private void swap(int[][] points, int i, int j) {
        int[] temp = points[i];
        points[i] = points[j];
        points[j] = temp;
    }
}

类型五：快速幂与矩阵

50. Pow(x, n)

题目：计算 $x$ 的 $n$ 次幂。

分析：利用 $x^n = x^{n/2} \cdot x^{n/2}$ 的性质，可以将乘法次数从 $O(n)$ 降到 $O(\log n)$。注意处理负指数和整数溢出。

Java 实现：

class Solution {
    public double myPow(double x, int n) {
        long N = n;
        if (N < 0) {
            x = 1 / x;
            N = -N;
        }
        return fastPow(x, N);
    }
    
    private double fastPow(double x, long n) {
        if (n == 0) return 1.0;
        
        double half = fastPow(x, n / 2);
        
        if (n % 2 == 0) {
            return half * half;
        } else {
            return half * half * x;
        }
    }
}

复杂度分析：$T(n) = T(n/2) + O(1)$，由主定理得 $O(\log n)$。

类型六：树与链表转换

426. 将二叉搜索树转化为排序双向链表

题目：将 BST 转化为排序的循环双向链表，要求原地操作。

分析：BST 的中序遍历结果是有序的。分治处理左右子树，然后将当前节点与左右子树转化后的链表连接。

Java 实现：

class Solution {
    public Node treeToDoublyList(Node root) {
        if (root == null) return null;
        
        // 分治处理左右子树
        Node leftHead = treeToDoublyList(root.left);
        Node rightHead = treeToDoublyList(root.right);
        
        // 当前节点形成自环
        root.left = root;
        root.right = root;
        
        // 连接左链表和当前节点
        leftHead = connect(leftHead, root);
        // 连接结果和右链表
        leftHead = connect(leftHead, rightHead);
        
        return leftHead;
    }
    
    private Node connect(Node a, Node b) {
        if (a == null) return b;
        if (b == null) return a;
        
        // 获取两个链表的尾节点
        Node aTail = a.left;
        Node bTail = b.left;
        
        // 连接 a 的尾部和 b 的头部
        aTail.right = b;
        b.left = aTail;
        
        // 连接 b 的尾部和 a 的头部（形成循环）
        bTail.right = a;
        a.left = bTail;
        
        return a;
    }
}

分治算法的适用边界

分治算法并非万能。它成功的关键在于两个条件：

最优子结构：原问题的最优解包含子问题的最优解。这要求问题可以被"干净地"分解，子问题之间相互独立。

分解与合并代价可控：分解问题和合并解的代价不能太高。如果 $f(n)$ 增长过快（如 $f(n) = n^2$），分治可能反而不如暴力解法。

一些问题天然不适合分治。例如，求解最长公共子序列（LCS）时，子问题之间存在大量重叠，分治会导致重复计算。这类问题更适合动态规划。

另一方面，当问题可以自然地分解成独立子问题，且合并代价线性或接近线性时，分治往往是首选策略。归并排序的稳定性和 $O(n \log n)$ 的保证、快速选择的平均线性复杂度、分治求逆序对的优雅性，都是分治思想的成功实践。

理解分治算法，本质上是理解一种解决问题的哲学：将困难分解，将简单积累。从 1945 年冯·诺依曼在 EDVAC 报告中描述归并排序开始，这一思想已经指导了计算机科学家近八十年。主定理提供了数学上的保证，而 Karatsuba、Strassen 等突破性工作则展示了分治策略的实际威力。

参考文献

Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press.
Bentley, J. L., Haken, D., & Saxe, J. B. (1980). A general method for solving divide-and-conquer recurrences. ACM SIGACT News, 12(3), 36-44.
Karatsuba, A., & Ofman, Y. (1963). Multiplication of multidigit numbers on automata. Soviet Physics Doklady, 7, 595-596.
Knuth, D. E. (1998). The Art of Computer Programming, Volume 3: Sorting and Searching (2nd ed.). Addison-Wesley.

分治的几何直观：递归树上的代价分配#

主定理：分治算法的复杂度速查表#

三种情况#

经典算法的主定理分析#

分治算法的历史突破#

LeetCode 分治题目分类与详解#

类型一：排序与选择#

148. 排序链表#

215. 数组中的第K个最大元素#

类型二：区间问题#

53. 最大子数组和#

315. 计算右侧小于当前元素的个数#

类型三：表达式与构造#

241. 为运算表达式设计优先级#

932. 漂亮数组#

类型四：几何与最近邻#

973. 最接近原点的 K 个点#

类型五：快速幂与矩阵#

50. Pow(x, n)#

类型六：树与链表转换#

426. 将二叉搜索树转化为排序双向链表#

分治算法的适用边界#

参考文献#

更多精彩内容

排序算法为何如此重要从快速排序到TimSort的八十年演进与LeetCode完整通关指南

扫描线算法如何将二维问题降维成一维从天际线到矩形面积的LeetCode完整通关指南

最长公共子序列为何能解决十几类LeetCode问题从字符串相似度到DNA比对的动态规划精髓

博弈论算法为何能用数学公式预测胜负从Nim博弈到极大极小算法的完整LeetCode通关指南

链表算法为何让无数开发者头疼从指针陷阱到快慢指针的完整LeetCode通关指南

分治的几何直观：递归树上的代价分配

主定理：分治算法的复杂度速查表

三种情况

经典算法的主定理分析

分治算法的历史突破

LeetCode 分治题目分类与详解

类型一：排序与选择

148. 排序链表

215. 数组中的第K个最大元素

类型二：区间问题

53. 最大子数组和

315. 计算右侧小于当前元素的个数

类型三：表达式与构造

241. 为运算表达式设计优先级

932. 漂亮数组

类型四：几何与最近邻

973. 最接近原点的 K 个点

类型五：快速幂与矩阵

50. Pow(x, n)

类型六：树与链表转换

426. 将二叉搜索树转化为排序双向链表

分治算法的适用边界

参考文献