sorting - 归并排序空间

Question

在自上而下的合并排序中，递归函数以这种方式调用:

void mergesort(Item a[], int l, int r) {
    if (r <= l) return;
    int m = (r+l)/2;
    mergesort(a, l, m);
    mergesort(a, m+1, r);
    merge(a, l, m, r);
}

教科书上给出了该策略的空间复杂度为O(n)。而如果我们仔细观察递归:我们在递归调用中传递指向数组的指针。其次，通过将底部节点合并到父节点，以遍历的先序顺序解决递归。所以每次都有 O(logn) 个变量在堆栈上(或 O(log n) 个帧在堆栈上)。那么，尽管采用了就地合并技术，空间复杂度为何仍为 O(n)？

Answer 1

So how is it that space complexity is O(n) inspite of having in-place merging techniques?

因为您书中给出的实现可能没有使用就地合并技术。如果需要 O(1) 空间和 O(n log n) 时间排序，通常首选堆排序而不是归并排序，因为它更容易。只有当您谈论排序列表时，进行 O(1) 合并排序才有意义……然后，这很容易做到。为例如指定的合并排序链表将是 O(1) 空间和 O(n log n) 时间。

这里的根本误解似乎是:时间复杂性适用于算法，而不是它们解决的问题。如果我愿意，我可以写一个 O(n^3) 合并排序......并不意味着我的算法不是 O(n^3)，它也没有说明你的 O(n log n) 合并种类。这与计算复杂性略有不同，我们在计算复杂性中讨论例如问题在 P 中...如果存在多项式时间算法，则问题在 P 中。但是，P 中的问题也可以通过非多项式时间算法来解决，如果您考虑一下，构建这样的算法是微不足道的。空间复杂度也是如此。