2

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

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)？

4

4 回答 4

4

那么，尽管有就地合并技术，空间复杂度如何为 O(n)？

因为您书中给出的实现可能没有使用就地合并技术。如果需要 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 中的问题也可以通过非多项式时间算法来解决，如果您考虑一下，构造这样的算法是微不足道的。空间复杂性也是如此。

于 2011-08-03T20:31:02.670 回答
2

你是对的，递归调用占用的空间是 O(log n)。

但是数组本身占用的空间是 O(n)。

总空间复杂度为 O(n) + O(log n)。

这是 O(n)，因为它以 (n)=>2(n) 为界。

于 2011-08-03T18:53:05.503 回答
1

你将如何在太空中存储n物品？log n那没有意义。如果您要对n物品进行分类，O(n)空间是您将获得的最佳选择。

于 2011-08-03T18:50:19.153 回答
0

由于除了常量之外，您没有在合并排序函数内分配任何空间，因此该函数的空间复杂度为 O(lg(n))。但是如果是数组，您的合并过程将分配内存，因此请记住它变为 O(lg(n)) + O(n) = O(n)。如果您使用链表，您可以避免合并过程中的暂存空间，因此最好达到 O(lg(n) 。

于 2012-04-19T00:52:15.087 回答