algorithm - 运行时空复杂度修改后的归并排序

Question

这是数据结构和算法类(class)的家庭作业问题。我不想让任何人为我做作业。只是希望有人能告诉我我是否正在适本地处理这个问题。

public static void sort(int[] a) {
  sort(a, 0, a.length - 1);
}

private static void sort(int[] a, int lo, int hi) {
  if (hi <= lo) return;

  int[] aux = new int[a.length];
  int mid = (hi + lo) / 2;
  sort(a, lo, mid);
  sort(a, mid + 1, hi);
  merge(a, lo, mid, hi, aux);
}

private static void merge(int[] a, int lo, int mid, 
 int hi, int[] aux) {

  int i = lo, j = mid + 1;
  for (int k = lo; k <= hi; k++)
    aux[k] = a[k];

  for (int k = lo; k <= hi; k++) {
    if (i > mid)
      a[k] = aux[j++];
    else if (j > hi)
      a[k] = aux[i++];
    else if(aux[j] < aux[i])
      a[k] = aux[j++];
    else
      a[k] = aux[i++];
  }
}

此实现与典型实现(已在我们的类(class)中给出)之间的唯一区别是辅助数组在每次递归调用排序时重新定义，而在典型的公共(public)排序方法中仅定义一次案件。典型情况的运行时间为 O(nlog(n))，空间复杂度为 O(n)。

我的任务是确定显示的合并排序修改实现的运行时间和空间复杂度。据我所知，运行时间没有改变，所以仍然是O(nlog(n))，空间复杂度也是O(nlog(n))。我得出这个结论的逻辑是sort方法每次调用都会分配一个大小为n的数组，一共调用了log(n)次。

到目前为止，我一直难以理解空间和时间的复杂性。我对这个问题的思考是否正确，还是偏离了方向？

非常感谢任何指点。

Answer 1

你是对的，空间复杂度是 O(n*logn)，但它需要一些说明。

My logic in coming to this conclusion is that the sort method allocates an array of size n each time it is called, and it is called a total of log(n) times.

实际上，sort在归并排序过程中一共调用了n次，但最大递归深度为logn。让我们画一棵递归调用树:

           sort
          /    \
       sort    sort
        /\       /\
     sort sort sort sort
            ...

在每个级别上，每个 sort 函数执行其父级的一半工作。因此，在第 0 级(根节点)上，sort 有 n 次迭代，在第 1 级上，每两个排序都有 n/2 运行时间(在一起是 n)，在第 2 层，四种类型中的每一种都有 n/4 等。组合起来，每个级别都进行 n 迭代，并且由于树的深度是 log n，你得到 O(n*logn) 时间复杂度。

但是，在您的情况下，aux 分配了 n 元素，而不管当前深度如何，并且有 n 次调用排序，所以在乍一看，可以得出空间复杂度为 O(n*n) = O(n^2) 的结论。 不是，因为一旦我们完成每个递归调用，分配的空间就会被释放，并且有最大的 logn 递归调用。

请注意，aux 不必要每次都分配 n 元素的数组。如果在 merge 函数中声明 aux 并设置适当的长度，则可以改进算法，如下所示:

private static void merge(int[] a, int lo, int mid, int hi) {

  int[] aux = new int[hi - lo + 1];     

  int i = lo, j = mid + 1;
  for (int k = lo; k <= hi; k++)
    aux[k - lo] = a[k];

  for (int k = lo; k <= hi; k++) {
    if (i > mid)
      a[k] = aux[j++ - lo];
    else if (j > hi)
      a[k] = aux[i++ - lo];
    else if(aux[j - lo] < aux[i - lo])
      a[k] = aux[j++ - lo];
    else
      a[k] = aux[i++ - lo];
  }
}

HTH.