递归和分治法

:::info 很多算法题和日常工作中遇到的一些问题，如菜单以及其子菜单的列表渲染在结构上是递归的。算法将一次或多次的调用自身。这遵循分治法的思想：将原问题拆分为类似的多个子问题，递归求解这些子问题再将子问题的解合并得到原问题的解。 :::

分治模式在每层递归时的三个步骤

  1. 将原问题分解为多个与原问题类似的子问题
  2. 递归求解各子问题
  3. 合并子问题得到原问题的解

归并排序的实现

工作方式

:::info 归并排序显然满足上面说的分治模式：

  1. 分解：将有n个元素待排序的序列分为各具有n/2个元素的两个子序列
  2. 解决：使用归并排序递归的排序两个子序列
  3. 合并：将所有子序列合并得到最终排序好的序列 :::

代码实现

  1. void merge(int arr[], int left, int mid, int right)
  2. {
  3.   int i = left, j = mid + 1, k = 0;
  4.   int *temp = new int[right - left + 1];
  5.   // 将arr[left,..., mid]和arr[mid + 1, right]两个数组里的元素按大小依次放入临时数组temp
  6.   while (i <= mid && j <= right)
  7.   {
  8.     if (arr[i] <= arr[j])
  9.     {
  10.       temp[k++] = arr[i++];
  11.     }
  12.     else
  13.     {
  14.       temp[k++] = arr[j++];
  15.     }
  16.   }
  17.   while (i <= mid)
  18.   {
  19.     temp[k++] = arr[i++];
  20.   }
  21.   while (j <= right)
  22.   {
  23.     temp[k++] = arr[j++];
  24.   }
  25.   for (i = left, k = 0; i <= right;)
  26.   {
  27.     // 将arr[left,...,right]按下标依次改为已排序好的temp数组里对应的值
  28.     arr[i++] = temp[k++];
  29.   }
  30.   delete[] temp;
  31. }
  32. void mergeSort(int arr[], int left, int right)
  33. {
  34.   if (left >= right)
  35.   {
  36.     return; // 递归终止条件
  37.   }
  38.   int mid = left + (right - left) / 2;
  39.   mergeSort(arr, left, mid);      // 分
  40.   mergeSort(arr, mid + 1, right); // 分
  41.   merge(arr, left, mid, right);   // 治
  42. }

复杂度分析

时间复杂度

:::warning T(n)是规模为n的一个问题的运行时间。若问题规模足够小，如对于某个常量c，n <= c，则直接求解时间为常量o(1)。
假如将原问题分为a个子问题，每个子问题的规模是原问题的1/b，对于归并排序a=b=2。求解一个规模为n/b的子问题需要T(n/b)的时间。则aT(n/b)是处理所有子问题的时间。如果分解问题的时间为D(n)，合并子问题成原问题的事件为C(n)。则：
image.png

  • 分解：计算数组中间位置mid为常量时间，因此D(n) = 1
  • 递归：递归求解规模为n/2的两个子问题，时间为2T(n/2)
  • 合并：在具有n个元素的数组上merge的过程需要的事件为o(n)，则C(n) = O(n)

image.png
去除主定理后得到的表达式：（其中c代表求解规模为1的问题所需时间以及在分解步骤和合并步骤每个处理每个数组元素所需的时间）
image.png
展开递归树：
image.png
时间复杂度为：o(nlgn) :::

空间复杂度

:::warning 空间复杂度并不是原地排序算法，merge过程中所有的temp数组大小相加为原数组的大小。
空间复杂度为n(n) :::

相关资料

<算法导论（第三版）>