跳到主要内容

分治思想

分治法是一种将原问题分解为多个规模较小的子问题，递归解决这些子问题，然后将子问题的解合并为原问题的解的算法设计思想。它非常适合那些可以通过分解和合并来解决的问题。

核心：​

  • 分解: 将问题分解为多个相同类型的子问题，子问题规模较原问题更小。
  • 递归求解: 递归地解决每个子问题，如果子问题足够小，则直接求解。
  • 合并: 将子问题的解合并，得到原问题的解。

工作原理：​

  • 递归树: 分治法的过程可以表示为一棵递归树，根节点为原问题，子节点为子问题。通过自顶向下展开，直至达到最小问题规模，然后自底向上合并解。

分治法要求严格最优子结构，因为其本质就是“子问题和问题有同样的解”。

  • 分治模板: 分治算法一般遵循以下模板：
    • 分解：将问题分解为规模较小的子问题。
    • 递归求解：递归地求解子问题。
    • 合并：将子问题的解合并为原问题的解。

典型问题​

1. 归并排序​

归并排序是一种稳定的排序算法，它采用分治法将待排序数组分为两半，递归地对子数组排序，然后将两个已排序的子数组合并为一个有序数组。

代码示例：

void merge(vector<int>& arr, int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;
    vector<int> L(n1), R(n2);
    for (int i = 0; i < n1; i++) L[i] = arr[left + i];
    for (int j = 0; j < n2; j++) R[j] = arr[mid + 1 + j];
    int i = 0, j = 0, k = left;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        } else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }
    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }
    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
}

void mergeSort(vector<int>& arr, int left, int right) {
    if (left >= right) return;
    int mid = left + (right - left) / 2;
    mergeSort(arr, left, mid);
    mergeSort(arr, mid + 1, right);
    merge(arr, left, mid, right);
}

在归并排序中，数组被反复分割，直到每个子数组的大小为1，然后再通过合并操作，将这些小数组逐步合并成一个排序后的数组。

2. 快速排序​

快速排序是另一种广泛使用的排序算法，它通过选择一个“基准”元素，将数组分为两个子数组，使得左边的元素都小于基准，右边的元素都大于基准，然后递归地对子数组进行排序。

代码示例：

int partition(vector<int>& arr, int low, int high) {
    int pivot = arr[high];
    int i = (low - 1);
    for (int j = low; j <= high - 1; j++) {
        if (arr[j] < pivot) {
            i++;
            swap(arr[i], arr[j]);
        }
    }
    swap(arr[i + 1], arr[high]);
    return (i + 1);
}

void quickSort(vector<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);
    }
}

在快速排序中，通过递归地将数组分割成两个部分，并分别排序，最终得到一个有序的数组。

3. 最大子数组问题​

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

这个问题可以通过分治法求解，将数组分为左右两半，然后递归解决左半部分、右半部分和跨越中点的部分，最后取三者的最大值。

代码示例：

int maxCrossingSum(vector<int>& arr, int left, int mid, int right) {
    int sum = 0;
    int left_sum = INT_MIN;
    for (int i = mid; i >= left; i--) {
        sum += arr[i];
        if (sum > left_sum)
            left_sum = sum;
    }

    sum = 0;
    int right_sum = INT_MIN;
    for (int i = mid + 1; i <= right; i++) {
        sum += arr[i];
        if (sum > right_sum)
            right_sum = sum;
    }

    return max(left_sum + right_sum, max(left_sum, right_sum));
}

int maxSubArraySum(vector<int>& arr, int left, int right) {
    if (left == right)
        return arr[left];

    int mid = (left + right) / 2;

    return max({maxSubArraySum(arr, left, mid),
                maxSubArraySum(arr, mid + 1, right),
                maxCrossingSum(arr, left, mid, right)});
}

分治法的优化​

  1. 减少递归层数: 分治法的效率主要依赖于递归的深度和每次分割所需的工作量，因此可以通过减少递归层数或优化分割过程来提升效率。
  2. 尾递归优化: 对于某些问题，可以通过尾递归优化减少栈空间的使用。
  3. 动态规划的结合: 在某些情况下，分治法和动态规划可以结合使用，特别是当子问题有重叠时，可以利用记忆化存储中间结果以减少计算。