########################################
算法设计
########################################

分治法
****************************************

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

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

#. **分解** 原问题为若干个子问题
#. **解决** 这些子问题。递归地求解子问题，当子问题的规模足够小时，直接求解子问题
#. **合并** 这些子问题以得到原问题的解

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

.. code-block:: cpp

    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);
        }
    }

分治法的需要的时间
========================================

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

.. math::

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