【信奥赛·算法基础】CSP-J 分治算法及C++示例

序言

想象一下，碰到一个特别难搞的大问题，就像面前有一座巨大的山，看着都吓人，根本不知道从哪儿下手。但我们可以把这座大山分成好多小块。这样一来，每个小块就比原来的大山小多了，也容易对付多啦。
分治算法把大问题变成一个个小问题后，这些小问题就跟原来的大问题差不多，但是简单多啦。然后咱们就可以一个一个地去解决这些小问题。等把小问题都解决完了，分治算法又像个神奇的魔法师，把这些小问题的答案拼在一起，就变成了大问题的答案。

一、定义与概念

分治算法（Divide and Conquer）是一种重要的算法设计策略。其核心思想是将一个大问题分解为多个规模较小、相互独立且与原问题形式相同的子问题，分别求解这些子问题，然后将子问题的解合并起来得到原问题的解。

二、基本步骤

1. 分解（Divide）：将原问题划分为若干个规模较小、相互独立且与原问题形式相同的子问题。例如，在归并排序中，将待排序的数组一分为二，得到两个规模减半的子数组。
2. 求解子问题（Conquer）：递归地求解各个子问题。如果子问题的规模足够小，则直接求解。例如，当子数组的长度为 1 时，该子数组已经是有序的，无需进一步排序。
3. 合并（Combine）：将子问题的解合并起来，得到原问题的解。在归并排序中，将两个已排序的子数组合并为一个有序的数组。

三、应用示例

归并排序

1. 问题描述：给定一个无序数组，将其按升序排列。
2. 分治过程：
   • 分解：将数组分成两个子数组，每个子数组的长度约为原数组的一半。
   • 求解子问题：对两个子数组分别进行归并排序，这是通过递归调用归并排序函数实现的。
   • 合并：将两个已排序的子数组合并为一个有序的数组。
3. C++ 代码实现：

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) {
        int mid = left + (right - left) / 2;
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
        merge(arr, left, mid, right);
    }
}

四、分治算法的特点与优势

1. 降低问题复杂度：通过将大问题分解为小问题，使得每个子问题的规模都小于原问题，从而降低了问题的复杂度。这使得分治算法能够有效地处理大规模问题。
2. 利用子问题的独立性：分治算法假设子问题之间是相互独立的，这使得可以并行地求解子问题，提高算法的效率。例如，在归并排序中，对两个子数组的排序可以同时进行。
3. 递归结构清晰：分治算法通常采用递归的方式实现，这种递归结构使得算法的逻辑清晰，易于理解和实现。同时，递归也可以利用系统的栈空间自动管理子问题的求解过程。
4. 适用于多种问题：分治算法适用于许多不同类型的问题，只要问题可以被分解为规模较小、形式相同的子问题，并且子问题的解可以合并得到原问题的解。