分治算法

分治算法（Divide and Conquer），顾名思义就是"分而治之"。它是一种重要的算法设计范式，通过将复杂问题分解为多个相似的子问题，递归求解后再合并结果，从而降低问题的复杂度。

核心思想

分治算法的核心思想可以概括为三个步骤：

分解（Divide）：将原问题分解为若干个规模较小、相互独立、与原问题形式相同的子问题。

解决（Conquer）：若子问题规模足够小则直接求解，否则递归地解决各个子问题。

合并（Combine）：将各个子问题的解合并为原问题的解。

这三个步骤形成了一个递归的结构。子问题与原问题具有相同的形式，只是规模更小，这正是递归思想在算法设计中的典型应用。

适用条件

并非所有问题都适合用分治策略解决。一个问题能否使用分治算法，需要满足以下条件：

1. 可分解性：问题可以分解为若干个规模较小的相同问题。这意味着问题的结构具有递归性质，子问题与原问题除了规模不同外，本质上是同一类问题。

2. 子问题独立：各子问题之间相互独立，不包含重叠的子问题。如果子问题之间存在重叠，使用分治算法会造成重复计算，此时动态规划可能是更好的选择。

3. 解可合并：子问题的解可以合并为原问题的解。合并操作的代价应当合理，不能太高以至于抵消分治带来的收益。

4. 基准情况：存在明确的基准情况（Base Case），当问题规模足够小时可以直接求解，从而终止递归。

经典算法对比

不同分治算法在三个步骤上的复杂度各有不同：

算法	分解	解决	合并	时间复杂度
二分查找	$O(1)$	1个子问题	$O(1)$	$O(\log n)$
归并排序	$O(1)$	2个子问题	$O(n)$	$O(n \log n)$
快速排序	$O(n)$	2个子问题	$O(1)$	$O(n \log n)$（平均）
Strassen矩阵乘法	$O(1)$	7个子问题	$O(n^2)$	$O(n^{2.81})$

注意：有些算法的某个步骤可能很简单。例如，二分查找的分解和合并步骤都是常数时间；快速排序的合并步骤实际上是空的，因为分区操作已经将元素放到了正确的位置。

归并排序

归并排序是分治算法最经典的实现之一，它完美展示了分治的三个步骤。

算法流程

1. 分解：将数组从中间分成两半
2. 解决：递归地对两个子数组进行排序
3. 合并：将两个已排序的子数组合并为一个有序数组

代码实现

public class MergeSort {
    
    /**
     * 归并排序主函数
     * @param arr 待排序数组
     */
    public static void mergeSort(int[] arr) {
        if (arr == null || arr.length <= 1) {
            return;
        }
        int[] temp = new int[arr.length];  // 辅助数组，避免频繁创建
        mergeSort(arr, 0, arr.length - 1, temp);
    }
    
    /**
     * 归并排序递归函数
     * @param arr 待排序数组
     * @param left 左边界
     * @param right 右边界
     * @param temp 辅助数组
     */
    private static void mergeSort(int[] arr, int left, int right, int[] temp) {
        // 基准情况：只有一个元素时，已经有序
        if (left >= right) {
            return;
        }
        
        // 分解：找到中间位置
        int mid = left + (right - left) / 2;  // 避免整数溢出
        
        // 解决：递归排序左右两部分
        mergeSort(arr, left, mid, temp);
        mergeSort(arr, mid + 1, right, temp);
        
        // 合并：将两个有序数组合并
        merge(arr, left, mid, right, temp);
    }
    
    /**
     * 合并两个有序数组
     * @param arr 原数组
     * @param left 左边界
     * @param mid 中间位置（左半部分的最后一个元素）
     * @param right 右边界
     * @param temp 辅助数组
     */
    private static void merge(int[] arr, int left, int mid, int right, int[] temp) {
        int i = left;      // 左半部分的起始位置
        int j = mid + 1;   // 右半部分的起始位置
        int k = 0;         // 临时数组的当前位置
        
        // 比较两部分的元素，将较小的放入临时数组
        while (i <= mid && j <= right) {
            if (arr[i] <= arr[j]) {
                temp[k++] = arr[i++];
            } else {
                temp[k++] = arr[j++];
            }
        }
        
        // 将左半部分剩余元素复制到临时数组
        while (i <= mid) {
            temp[k++] = arr[i++];
        }
        
        // 将右半部分剩余元素复制到临时数组
        while (j <= right) {
            temp[k++] = arr[j++];
        }
        
        // 将临时数组的元素复制回原数组
        for (i = 0; i < k; i++) {
            arr[left + i] = temp[i];
        }
    }
    
    public static void main(String[] args) {
        int[] arr = {38, 27, 43, 3, 9, 82, 10};
        System.out.println("排序前: " + Arrays.toString(arr));
        
        mergeSort(arr);
        
        System.out.println("排序后: " + Arrays.toString(arr));
    }
}

执行过程示例

以数组 [38, 27, 43, 3, 9, 82, 10] 为例：

分解过程（自顶向下）：
[38, 27, 43, 3, 9, 82, 10]
        ↓
[38, 27, 43]    [3, 9, 82, 10]
    ↓               ↓
[38] [27, 43]   [3, 9] [82, 10]
      ↓           ↓       ↓
    [27][43]    [3][9]  [82][10]

合并过程（自底向上）：
[27, 43] ← [27][43]
[3, 9] ← [3][9]
[82, 10] ← [82][10]
    ↓
[27, 38, 43] ← [38][27, 43]
[3, 9, 10, 82] ← [3, 9][82, 10]
    ↓
[3, 9, 10, 27, 38, 43, 82] ← [27, 38, 43][3, 9, 10, 82]

复杂度分析

时间复杂度：$O(n \log n)$

分解操作是常数时间，递归深度为 $\log n$ 层，每层的合并操作总时间复杂度为 $O(n)$，因此总时间复杂度为 $O(n \log n)$。无论最好、最坏还是平均情况，归并排序的时间复杂度都是 $O(n \log n)$，这是它相对于快速排序的优势。

空间复杂度：$O(n)$

需要一个与原数组大小相同的辅助数组用于合并操作。递归调用栈的深度为 $O(\log n)$，但与辅助数组相比可以忽略。

快速排序

快速排序同样基于分治思想，但它的分治策略与归并排序有所不同。

算法流程

1. 分解（分区）：选择一个基准元素（pivot），将数组分为两部分，左边元素都小于基准，右边元素都大于基准
2. 解决：递归地对左右两部分进行排序
3. 合并：无需合并，分区操作已经将元素放到正确位置

代码实现

public class QuickSort {
    
    public static void quickSort(int[] arr) {
        if (arr == null || arr.length <= 1) {
            return;
        }
        quickSort(arr, 0, arr.length - 1);
    }
    
    private static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            // 分区操作，返回基准元素的最终位置
            int pivotIndex = partition(arr, low, high);
            
            // 递归排序左右两部分
            quickSort(arr, low, pivotIndex - 1);
            quickSort(arr, pivotIndex + 1, high);
        }
    }
    
    /**
     * 分区函数：将数组分为两部分，返回基准元素的最终位置
     */
    private static int partition(int[] arr, int low, int high) {
        int pivot = arr[high];  // 选择最后一个元素作为基准
        int i = low - 1;        // i 指向小于基准的区域的最后一个元素
        
        for (int j = low; j < high; j++) {
            if (arr[j] <= pivot) {
                i++;
                swap(arr, i, j);
            }
        }
        
        // 将基准元素放到正确位置
        swap(arr, i + 1, high);
        return i + 1;
    }
    
    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

复杂度分析

时间复杂度：

• 平均情况：$O(n \log n)$
• 最坏情况：$O(n^2)$（当数组已经有序或逆序，且每次选择第一个或最后一个元素作为基准时）

空间复杂度：$O(\log n)$（递归调用栈的平均深度）

归并排序 vs 快速排序

特性	归并排序	快速排序
时间复杂度	始终 $O(n \log n)$	平均 $O(n \log n)$，最坏 $O(n^2)$
空间复杂度	$O(n)$	$O(\log n)$
稳定性	稳定	不稳定
合并步骤	需要	不需要
适用场景	链表排序、外部排序	数组排序、内存排序

在实际应用中，快速排序通常是更好的选择，因为它的常数因子更小，且是原地排序。但在需要稳定排序或处理大数据（外部排序）时，归并排序更有优势。

主定理

主定理（Master Theorem）是分析分治算法时间复杂度的有力工具。对于形如 $T(n) = aT(n/b) + f(n)$ 的递归关系，可以直接给出渐进时间复杂度。

递归关系的含义

$T(n) = aT(n/b) + f(n)$

• $a \geq 1$：每次递归产生的子问题数量
• $b > 1$：子问题规模缩小的倍数（每个子问题的规模为 $n/b$）
• $f(n)$：分解问题和合并子问题的代价

三种情况

定义临界指数 $c_{crit} = \log_b a$，这表示递归树叶子节点的增长率。

情况一：$f(n) = O(n^{c_{crit} - \epsilon})$，其中 $\epsilon > 0$

如果合并代价 $f(n)$ 多项式级别地小于 $n^{c_{crit}}$，说明叶子节点的代价占主导。

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

情况二：$f(n) = \Theta(n^{c_{crit}} \log^k n)$，其中 $k \geq 0$

如果合并代价与叶子节点代价相当，两者都对总时间有贡献。

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

当 $k = 0$ 时，$T(n) = \Theta(n^{\log_b a} \log n)$

情况三：$f(n) = \Omega(n^{c_{crit} + \epsilon})$，其中 $\epsilon > 0$，且满足正则条件 $af(n/b) \leq cf(n)$

如果合并代价多项式级别地大于叶子节点代价，说明合并代价占主导。

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

应用案例

案例一：归并排序

$T(n) = 2T(n/2) + n$

• $a = 2, b = 2, f(n) = n$
• $c_{crit} = \log_2 2 = 1$
• $f(n) = n = \Theta(n^1) = \Theta(n^{c_{crit}})$

符合情况二（$k = 0$），因此 $T(n) = \Theta(n \log n)$

案例二：二分查找

$T(n) = T(n/2) + 1$

• $a = 1, b = 2, f(n) = 1$
• $c_{crit} = \log_2 1 = 0$
• $f(n) = 1 = \Theta(n^0) = \Theta(n^{c_{crit}})$

符合情况二（$k = 0$），因此 $T(n) = \Theta(\log n)$

案例三：Strassen 矩阵乘法

$T(n) = 7T(n/2) + n^2$

• $a = 7, b = 2, f(n) = n^2$
• $c_{crit} = \log_2 7 \approx 2.81$
• $f(n) = n^2 = O(n^{2.81 - \epsilon})$（取 $\epsilon = 0.81$）

符合情况一，因此 $T(n) = \Theta(n^{\log_2 7}) = \Theta(n^{2.81})$

案例四：某递归算法

$T(n) = 3T(n/4) + n^2$

• $a = 3, b = 4, f(n) = n^2$
• $c_{crit} = \log_4 3 \approx 0.79$
• $f(n) = n^2 = \Omega(n^{0.79 + \epsilon})$（取 $\epsilon = 1.21$）
• 验证正则条件：$3(n/4)^2 = 3n^2/16 \leq cn^2$（$c = 1/4$ 即可）

符合情况三，因此 $T(n) = \Theta(n^2)$

主定理的局限性

主定理不适用于以下情况：

1. $a$ 不是常数，如 $a = n$
2. $f(n)$ 不是多项式，如 $f(n) = 2^n$
3. $T(n)$ 不是单调的，如 $T(n) = \sin n$

对于这些情况，需要使用递归树方法或代入法进行分析。

二分查找

二分查找是分治思想的简单应用，虽然它的实现很简单，但很好地体现了分治的核心思想。

算法思想

在有序数组中查找目标值时，每次将搜索范围缩小一半：

1. 找到中间元素
2. 如果中间元素等于目标值，返回
3. 如果中间元素大于目标值，在左半部分继续查找
4. 如果中间元素小于目标值，在右半部分继续查找

代码实现

public class BinarySearch {
    
    /**
     * 二分查找（递归实现）
     * @return 目标值的索引，不存在返回 -1
     */
    public static int binarySearch(int[] arr, int target) {
        return binarySearch(arr, target, 0, arr.length - 1);
    }
    
    private static int binarySearch(int[] arr, int target, int left, int right) {
        // 基准情况：搜索范围为空
        if (left > right) {
            return -1;
        }
        
        int mid = left + (right - left) / 2;
        
        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] > target) {
            return binarySearch(arr, target, left, mid - 1);
        } else {
            return binarySearch(arr, target, mid + 1, right);
        }
    }
    
    /**
     * 二分查找（迭代实现）
     */
    public static int binarySearchIterative(int[] arr, int target) {
        int left = 0, right = arr.length - 1;
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            
            if (arr[mid] == target) {
                return mid;
            } else if (arr[mid] > target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        
        return -1;
    }
}

复杂度分析

时间复杂度：$O(\log n)$。每次递归调用都将问题规模减半，递归深度为 $\log n$。

空间复杂度：递归实现为 $O(\log n)$（递归栈），迭代实现为 $O(1)$。

最大子数组和

LeetCode 53：给定一个整数数组 nums，找到一个具有最大和的连续子数组，返回其最大和。

分治解法

将数组从中间分成两半，最大子数组要么完全在左半部分，要么完全在右半部分，要么跨越中间。我们分别求出这三种情况的最大值，然后取最大者。

public class MaximumSubarray {
    
    public static int maxSubArray(int[] nums) {
        return maxSubArray(nums, 0, nums.length - 1);
    }
    
    private static int maxSubArray(int[] nums, int left, int right) {
        // 基准情况：只有一个元素
        if (left == right) {
            return nums[left];
        }
        
        int mid = left + (right - left) / 2;
        
        // 情况1：最大子数组在左半部分
        int leftMax = maxSubArray(nums, left, mid);
        
        // 情况2：最大子数组在右半部分
        int rightMax = maxSubArray(nums, mid + 1, right);
        
        // 情况3：最大子数组跨越中间
        int crossMax = maxCrossing(nums, left, mid, right);
        
        // 返回三者中的最大值
        return Math.max(Math.max(leftMax, rightMax), crossMax);
    }
    
    /**
     * 计算跨越中间的最大子数组和
     */
    private static int maxCrossing(int[] nums, int left, int mid, int right) {
        // 从中间向左扫描，找到最大和
        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;
    }
}

复杂度分析

时间复杂度：$O(n \log n)$。递归深度为 $\log n$，每层的跨中计算为 $O(n)$。

空间复杂度：$O(\log n)$（递归栈深度）。

虽然分治解法的时间复杂度高于动态规划的 $O(n)$ 解法（Kadane算法），但分治解法展示了分治思想在非排序问题上的应用，且分治解法天然支持并行计算。

多数元素

LeetCode 169：给定一个大小为 n 的数组，找出其中的多数元素。多数元素是指在数组中出现次数大于 $\lfloor n/2 \rfloor$ 的元素。

分治解法

如果数组中存在多数元素，那么将数组分成两半后，多数元素必定至少在其中一半中也是多数元素。

public class MajorityElement {
    
    public static int majorityElement(int[] nums) {
        return majorityElement(nums, 0, nums.length - 1);
    }
    
    private static int majorityElement(int[] nums, int left, int right) {
        // 基准情况：只有一个元素
        if (left == right) {
            return nums[left];
        }
        
        int mid = left + (right - left) / 2;
        
        // 分别求左右两部分的多数元素
        int leftMajor = majorityElement(nums, left, mid);
        int rightMajor = majorityElement(nums, mid + 1, right);
        
        // 如果两边的多数元素相同，直接返回
        if (leftMajor == rightMajor) {
            return leftMajor;
        }
        
        // 否则统计两个候选者在当前范围内的出现次数
        int leftCount = count(nums, leftMajor, left, right);
        int rightCount = count(nums, rightMajor, left, right);
        
        return leftCount > rightCount ? leftMajor : rightMajor;
    }
    
    private static int count(int[] nums, int target, int left, int right) {
        int count = 0;
        for (int i = left; i <= right; i++) {
            if (nums[i] == target) {
                count++;
            }
        }
        return count;
    }
}

复杂度分析

时间复杂度：$O(n \log n)$。递归深度为 $\log n$，每层需要统计次数，最坏情况 $O(n)$。

空间复杂度：$O(\log n)$（递归栈深度）。

数组中的第 K 个最大元素

LeetCode 215：在未排序的数组中找到第 k 个最大的元素。

快速选择算法

快速选择是快速排序的变种，利用分区操作快速定位第 k 大的元素。

public class KthLargest {
    
    public static int findKthLargest(int[] nums, int k) {
        // 第 k 大 = 第 (n - k + 1) 小
        return quickSelect(nums, 0, nums.length - 1, nums.length - k);
    }
    
    private static 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) {
            // 刚好找到第 k 小的元素
            return nums[pivotIndex];
        } else if (pivotIndex < k) {
            // 在右半部分继续查找
            return quickSelect(nums, pivotIndex + 1, right, k);
        } else {
            // 在左半部分继续查找
            return quickSelect(nums, left, pivotIndex - 1, k);
        }
    }
    
    private static 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 static void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

复杂度分析

时间复杂度：

• 平均：$O(n)$。每次分区后，问题规模大约减半。
• 最坏：$O(n^2)$。当每次分区都极其不平衡时。

空间复杂度：$O(1)$（原地分区）或 $O(\log n)$（递归栈深度）。

合并 K 个升序链表

LeetCode 23：合并 k 个已排序的链表，返回合并后的排序链表。

分治解法

将 k 个链表分成两半，分别合并，然后将两个合并后的链表再合并。这与归并排序的合并过程类似。

public class MergeKLists {
    
    public static class ListNode {
        int val;
        ListNode next;
        ListNode(int val) { this.val = val; }
    }
    
    public static ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) {
            return null;
        }
        return merge(lists, 0, lists.length - 1);
    }
    
    private static ListNode merge(ListNode[] lists, int left, int right) {
        // 基准情况：只有一个链表
        if (left == right) {
            return lists[left];
        }
        
        int mid = left + (right - left) / 2;
        
        // 分别合并左右两部分
        ListNode l1 = merge(lists, left, mid);
        ListNode l2 = merge(lists, mid + 1, right);
        
        // 合并两个有序链表
        return mergeTwoLists(l1, l2);
    }
    
    private static ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
        ListNode current = dummy;
        
        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                current.next = l1;
                l1 = l1.next;
            } else {
                current.next = l2;
                l2 = l2.next;
            }
            current = current.next;
        }
        
        current.next = (l1 != null) ? l1 : l2;
        
        return dummy.next;
    }
}

复杂度分析

假设每个链表的平均长度为 n，共有 k 个链表。

时间复杂度：$O(nk \log k)$。递归深度为 $\log k$，每层需要合并所有链表，总共 $O(nk)$。

空间复杂度：$O(\log k)$（递归栈深度）。

分治与其他算法策略的对比

策略	核心思想	适用条件	典型算法
分治	将问题分解为独立子问题	子问题独立、可合并	归并排序、快速排序
动态规划	将问题分解为重叠子问题，存储子问题的解	子问题重叠、最优子结构	最长公共子序列、背包问题
贪心	每步选择局部最优	局部最优导致全局最优	霍夫曼编码、最小生成树
回溯	系统地搜索所有可能的解	需要遍历解空间	八皇后、全排列

小结

分治算法是一种强大的算法设计范式，其核心思想是将大问题分解为小问题，分别解决后再合并结果。掌握分治算法需要注意以下几点：

1. 识别分治适用条件：问题可以分解为独立子问题，且子问题的解可以合并。

2. 理解三个步骤：分解、解决、合并。不同算法在这三个步骤上的复杂度分配不同。

3. 掌握主定理：用于快速分析分治算法的时间复杂度，理解三种情况的区别。

4. 注意边界条件：递归必须有明确的基准情况，否则会导致无限递归。

5. 对比其他策略：分治适用于子问题独立的情况，动态规划适用于子问题重叠的情况。

分治思想在算法设计中应用广泛，从经典的排序算法到现代的并行计算框架，都能看到分治思想的身影。理解分治的本质，有助于我们在面对复杂问题时，能够合理地分解问题，设计高效的解决方案。