桂帖 gui-forum

一、分治法的核心思想

分治法遵循三个基本步骤：

1. 分解：将原问题分解为若干个规模较小的子问题

2. 解决：递归地解决这些子问题

3. 合并：将子问题的解合并为原问题的解

二、分治法的经典应用

1. 排序算法

归并排序（Merge Sort）

void mergeSort(int[] arr, int l, int r) {
    if (l < r) {
        int m = l + (r - l)/2;
        mergeSort(arr, l, m);    // 排序左半部分
        mergeSort(arr, m+1, r);  // 排序右半部分
        merge(arr, l, m, r);     // 合并
    }
}

特点：

• 时间复杂度：O(n log n)

• 稳定排序

• 需要额外O(n)空间

快速排序（Quick Sort）

void quickSort(int[] arr, int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high); // 分区操作
        quickSort(arr, low, pi-1);  // 排序左子数组
        quickSort(arr, pi+1, high); // 排序右子数组
    }
}

特点：

• 平均时间复杂度：O(n log n)

• 原地排序（空间复杂度O(log n)递归栈）

• 不稳定排序

2. 搜索算法

二分查找

int binarySearch(int[] arr, int l, int r, int x) {
    if (r >= l) {
        int mid = l + (r - l)/2;
        if (arr[mid] == x) return mid;
        if (arr[mid] > x) return binarySearch(arr, l, mid-1, x);
        return binarySearch(arr, mid+1, r, x);
    }
    return -1;
}

特点：

• 时间复杂度：O(log n)

• 要求输入必须是有序数组

三、分治法与动态规划的区别

四、分治法的实现要点

1. 递归基（Base Case）：明确最简单情况的处理方法

2. 分解策略：如何将问题划分为子问题

3. 合并策略：如何将子问题的解合并

4. 效率优化：

   • 当问题规模足够小时，改用简单方法

   • 避免重复计算（特别是与动态规划结合时）

五、分治法的局限性

1. 递归开销：递归深度过大可能导致栈溢出

2. 不适合重叠子问题：会导致重复计算，效率低下

3. 分解合并成本：某些问题分解/合并的成本可能很高

4. 并行限制：并非所有分治算法都容易并行化