7

考虑一下，在包含元素的情况下Merge Sort，int Array我们n需要一个额外的大小数组n来执行合并。尽管我们最终丢弃了额外的数组。所以合并排序的空间复杂度是O(n)。但是如果你看一下递归mergeSort过程，每次递归调用都会将mergeSort(something)一个堆栈帧添加到堆栈中。它确实需要一些空间，对吧？

public static void mergeSort(int[] a,int low,int high)
{
    if(low<high)
    {
        int mid=(low+high)/2;
        mergeSort(a,low,mid);
        mergeSort(a,mid+1,high);
        merge(a,mid,low,high);
    }
}

我的问题是：

  1. 为什么我们在计算合并排序复杂度时不考虑堆栈帧的大小？
  2. 是不是因为堆栈只包含几个整数变量和一个引用，不占用太多内存？
  3. 如果我的递归函数创建了一个新的本地数组（比如说int a[]=new int [n];）。那么在计算空间复杂度时会考虑它吗？
4

2 回答 2

4

堆栈消耗的空间绝对应该被考虑在内，但有些人可能不同意这里（我相信一些算法甚至提出了忽略这一点的复杂性声明——关于基数排序漂浮在这里某处的未回答的相关问题）。

由于我们在每次递归调用时将数组分成两半，因此堆栈的大小将为O(log n).

因此，如果我们将其考虑在内，总空间将为O(n + log n)，这只是O(n)（因为，在大 O 表示法中，我们可以丢弃渐近更小的项），所以它不会改变复杂性。

对于创建本地数组，适用类似的论点。如果您在每一步都创建一个本地数组，那么您最终会得到O(n + n/2 + n/4 + n/8 + ...) = O(2n) = O(n)（因为在大 O 表示法中，我们可以丢弃常数因子），因此这也不会改变复杂性。

于 2013-12-24T11:43:18.820 回答
1

因为当你这样做时，你并没有计算空间复杂度。这就是所谓的确定：你正在做测试，并试图通过查看结果来得出空间复杂度的结论。这不是一种数学方法。

是的，你对陈述 2 是正确的。

于 2013-12-24T11:31:25.093 回答