为什么我们不考虑堆栈帧大小而计算递归过程的空间复杂度？

Question

考虑的情况下,Merge Sort对一个int Array含有n元素,我们需要大小的附加阵列n,以便执行merges.We丢弃到底附加阵列though.So归并排序的空间复杂度出来是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];),那该怎么办呢.那么在计算空间复杂度时会考虑它吗？

Answer 1

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

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

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

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