算法设计

分治法

将原问题分解为几个规模更小的子问题，递归地求解这些子问题，然后通过合并这些子问题来建立原问题的解，这种方法就是 分治法。

分治法在每层递归时都有三个步骤：

1. 分解 原问题为若干个子问题

2. 解决 这些子问题。递归地求解子问题，当子问题的规模足够小时，直接求解子问题

3. 合并 这些子问题以得到原问题的解

其中， 归并排序 完全符合分治法：

void merge(int arr[], int start, int mid, int end) {
    int ln = mid - start + 1;
    int rn = end - mid;
    int left[ln], right[rn];

    for (int i = 0; i < ln; i++) left[i] = arr[start + i];
    for (int j = 0; j < rn; j++) right[j] = arr[mid + j +1];
    int i = 0;
    int j = 0;
    int k = start;
    while (i < ln && j < rn) {
        if (left[i] <= right[j]) {
            arr[k] = left[i];
            i++;
        } else {
            arr[k] = right[j];
            j++;
        }
        k++;
    }
    while (i < ln) {
        arr[k] = left[i];
        i++;
        k++;
    }
    while (j < rn) {
        arr[k] = right[j];
        j++;
        k++;
    }
}

void mergeSort(int arr[], int start, int end) {
    if (start < end) {
        int mid = start + (end - start) / 2;
        mergeSort(arr, start, mid);
        mergeSort(arr, mid + 1, end);
        merge(arr, start, mid, end);
    }
}

分治法的需要的时间

假设 \(T(n)\) 是规模为 \(n\) 的一个问题的运行时间，对于规模足够小的问题（此时 \(n <= c\) ）求解需要的时间为 \(O(1)\) ，将原问题分解为 \(a\) 个子问题，每个子问题是原问题规模的 \(\frac{1}{b}\)；分解子问题需要的时间为 \(D(n)\) ，合并解需要的时间为 \(C(n)\) 。则：

\[\begin{split}\left\{ \begin{array}{lcr} O(1) && n \leq c\\ aT(\frac{n}{b}) + D(n)+C(n) && n \ge c \end{array} \right.\end{split}\]