合并排序时间和空间复杂度

Question

合并排序时间和空间复杂度

algorithmtime-complexitymergesortspace-complexity

48

让我们以这个归并排序的实现为例

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

a) 这个归并排序的时间复杂度是 O(n lg(n))。将步骤 (1) 和 (2) 并行化是否会带来实际收益？理论上看，即使并行化了这两部分，你最终仍然会得到 O(n lg(n))。但在实践中，我们能否获得任何收益呢？

b) 这个归并排序的空间复杂度是 O(n)。然而，如果我选择使用链表执行原地归并排序（不确定是否可以用数组合理地完成），那么空间复杂度会变成 O(lg(n))，因为您必须考虑递归栈帧大小。

我们能把 O(lg(n)) 视为常数吗，因为它不能超过 64 吗？我可能在几个地方误解了这一点。64 的确切含义是什么？

c) Cprogramming.com 的排序算法比较表明，使用链表的归并排序需要恒定的空间。怎么做到的？他们把 O(lg(n)) 视为常数了吗？

d) 添加以获得更多澄清。 在空间复杂度计算中，假设输入的数组或列表已经在内存中，这样公平吗？当我进行复杂度计算时，我总是计算除了输入已经占用的空间外，我还需要多少“额外”空间。否则，空间复杂度将始终是 O(n) 或更糟。

- Frank Q.

1

这篇回答对于一些概念会很有帮助：http://stackoverflow.com/a/35050103/550393 - 2cupsOfTech

7个回答

37

a) 在理想情况下，您需要对大小为n、n/2、n/4...（或者更确切地说是1、2、3...n/4、n/2、n - 它们无法并行化）进行log n次合并，这需要O(n)。但实际情况下，您没有无限数量的处理器，并且上下文切换和同步会抵消任何可能的收益。

b) 空间复杂度总是Ω(n)，因为您必须在某个地方存储元素。使用数组的实现的额外空间复杂度可以是O(n)，而使用链接列表实现的额外空间复杂度可以是O(1)。实际上，使用列表的实现需要额外的空间来存储列表指针，因此除非您已经将列表存储在内存中，否则这并不重要。

编辑如果计算堆栈帧，则为O(n)+ O(log n)，所以在数组的情况下仍为O(n)。在列表的情况下，额外的内存为O(log n)。

c) 列表在合并过程中只需要改变一些指针。这需要恒定的额外内存。

d) 这就是为什么在归并排序的复杂度分析中人们提到“额外的空间要求”之类的东西。显然，您必须在某个地方存储元素，但最好提到“额外的内存”来使纯粹主义者满意。

- soulcheck

1

从纯粹的角度来看，是的。当可以从上下文中推断出时，它并不是必需的，但如果有人因为没有提到而在考试中失分，我也不会感到惊讶。关于堆栈帧，通常会被省略，但可能会占用相当多的空间，虽然在数组实现中仍然是O(n)。 - soulcheck

你能解释一下为什么栈帧所需的大小是O(log n)吗？在每个级别上，递归调用的数量是2^j，因此栈帧的数量不应该是1 + 2 + 4 + .. + 2^((log n)+1)吗？我知道我漏掉了什么，但就是想不出来。我的疑问与额外的数组空间类似。在第0级，我们将大小为n的数组合并，而在第1级，我们将两个大小为n/2的数组合并，因此总分配量=2*n/2=n。因此，如果我们按照这种方式进行分析，它应该是n + n (log n次) = (n(log n))。我的分析有什么缺陷吗？ - Ayush Chaudhary

在堆栈大小分析中，您假设合并将同时进行，而实际上每次只能有O(log n)个递归调用堆叠。此外，重要的不是分配计数（双关语），而是一次分配的内存大小。您可以随意分配/释放，但每次额外分配的内存不会超过O(n)。 - soulcheck

1

@soulcheck 你所说的“在某个递归调用中”，是指什么时间？由于同一块内存稍后可以被重复使用，因此我们只需要查看在某个时间分配的最大大小（即在递归树的根处）？我无法理解答案的另一部分。虽然有O(logn)级别，但每个级别都会进行2^(levelnumber)次递归调用，对吗？根节点需要1个堆栈帧，但由于它在每个半部分上都进行了递归调用，因此两个半部分都需要在堆栈帧中存储，使要求在第1级别为2^1，在最后一级别时，它将是2^logn？ - Ayush Chaudhary

1

@AyushChaudhary 对不起，你是对的。我需要再次理解一下它。无论如何，它仍然是O(n)。我会更正答案。 - soulcheck

显示剩余4条评论

2

简单而聪明的思考。

总层数(L) = log2(N)。在最后一层节点数为N。

步骤1：假设所有层(i)的节点数为x(i)。

步骤2：因此时间复杂度= x1 + x2 + x3 + x4 + .... + x(L-1) + N（i = L）;

步骤3：实际上我们知道，x1,x2,x3,x4 ..., x(L-1) < N

步骤4：所以让我们考虑x1=x2=x3=...=x(L-1)=N

步骤5：因此时间复杂度= (N+N+N+..(L)次)

时间复杂度= O(N*L); 将L = log(N);

时间复杂度= O(N*log(N))

在合并时我们使用额外的数组，因此空间复杂度：O(N)。

提示：大O(x)时间意味着x是最小时间，我们可以确定地证明，在平均情况下它永远不会超过x

- Vivek Korat

1

合并排序的最坏情况性能：O(n log n)，合并排序的最佳情况性能：通常为O(n log n)，自然变体为O(n)，合并排序的平均性能：O(n log n)，合并排序的最坏情况空间复杂度：总共是O(n)，辅助空间是O(n)。

- Sourabh

1

a) 当然可以并行化归并排序，这样做非常有益。它仍然是nlogn的，但你的常数应该会显著降低。

b) 使用链表的空间复杂度应该是O(n)，更具体地说是O(n)+O(logn)。请注意，这是一个+而不是*。在渐近分析时，不要过多关注常数。

c) 在渐近分析中，只有方程中占主导地位的项才重要，因此我们使用的是+而不是*，使得时间复杂度为O(n)。如果我们一直复制子列表，我相信空间复杂度会是O(nlogn) - 但是，一个聪明的基于链表的归并排序可以共享列表的某些区域。

- user1277476

对于（b）使用链表的空间复杂度不是O（n），在排序的合并过程中不需要额外的空间，可以移动指针并执行原地合并。 - Frank Q.

你必须将列表的n个元素存储在某个地方。 - user1277476

不一定需要使用链表。 - Frank Q.

0

对于最好和最坏的情况，复杂度都是O(nlog(n))。虽然每一步需要额外的N大小的数组，因此空间复杂度为O(n+n)，即O(2n)。由于我们移除常数值来计算复杂度，因此它是O(n)。

- fuad ashraful

-1

归并排序的空间复杂度为O(nlogn)，这是很明显的，因为它最多可以进行O(logn)次递归，并且每次递归都需要额外的O(n)空间来存储需要重新分配的合并数组。对于那些认为是O(n)的人，请不要忘记它是O(n)的每个堆栈帧深度。

- Manjunath Bhadrannavar

2

合并后的数组在每个递归步骤之后都不会被垃圾回收吗？那么它应该是O(n)空间复杂度，而不是O(nlogn)。 - Kalyan Raghu

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Chee Loong Soon · Accepted Answer

MergeSort的时间复杂度是O(nlgn)，这是一项基本知识。 Merge Sort的空间复杂度始终为O(n)，包括数组在内。如果你将空间树画出来，看起来空间复杂度是O(nlgn)。然而，由于代码是深度优先的，你总是只会沿着树的一个分支扩展，因此，所需的总空间使用量始终受到O(3n) = O(n)的限制。

2023年10月24日更新：有一个关于我如何得出3n上界的问题。我在评论中解释了一下，现在重新粘贴在这里。数学上证明3n的方法与为未排序数组构建堆的时间复杂度为2n次交换的原因非常相似，这需要O(2n) = O(n)的时间。在这种情况下，总是只有一个额外的分支。因此，可以将其视为为1个额外的分支再次构建堆。因此，它将受到另外n的限制，总的上界为3n，即O(3n) = O(n)。请注意，在这种情况下，我们使用了构建堆（inputArray）时间复杂度的类似数学方法来证明单线程mergeSort的空间复杂度，而不是时间复杂度。我有时间时可以提供一个完整而严谨的数学证明。

构建堆如何具有O(n)的时间复杂度？

例如，如果你将空间树画出来，似乎是O(nlgn)的复杂度。

                             16                                 | 16
                            /  \                              
                           /    \
                          /      \
                         /        \
                        8          8                            | 16
                       / \        / \
                      /   \      /   \
                     4     4    4     4                         | 16
                    / \   / \  / \   / \
                   2   2 2   2.....................             | 16
                  / \  /\ ........................
                 1  1  1 1 1 1 1 1 1 1 1 1 1 1 1 1              | 16

当树的高度为O(logn)时，空间复杂度为O(nlogn + n) = O(nlogn)。然而，在实际代码中并非如此，因为它不是并行执行的。例如，在N = 16的情况下，这是mergesort代码的执行方式。N = 16。

注意到使用的空间数量为32 = 2n = 2*16 < 3n。

然后它向上合并。

这是34 < 3n。然后它向上合并

36 < 16 * 3 = 48

然后它向上合并

16 + 16 + 14 = 46 < 3*n = 48

in a larger case, n = 64

这是一个例子，其中 643 <= 3n = 3*64。

你可以通过归纳法来证明这个一般情况。

因此，即使你使用数组实现，并且在合并后清理已使用的空间，并且不并行执行代码而是按顺序执行，空间复杂度始终受到 O(3n) = O(n) 的限制。

下面是我的实现示例：

templace<class X> 
void mergesort(X a[], int n) // X is a type using templates
{
    if (n==1)
    {
        return;
    }
    int q, p;
    q = n/2;
    p = n/2;
    //if(n % 2 == 1) p++; // increment by 1
    if(n & 0x1) p++; // increment by 1
        // note: doing and operator is much faster in hardware than calculating the mod (%)
    X b[q];

    int i = 0;
    for (i = 0; i < q; i++)
    {
        b[i] = a[i];
    }
    mergesort(b, i);
    // do mergesort here to save space
    // https://dev59.com/_2kv5IYBdhLWcg3wzj01#28641693
    // After returning from previous mergesort only do you create the next array.
    X c[p];
    int k = 0;
    for (int j = q; j < n; j++)
    {
        c[k] = a[j];
        k++;
    }
    mergesort(c, k);
    int r, s, t;
    t = 0; r = 0; s = 0;
    while( (r!= q) && (s != p))
    {
        if (b[r] <= c[s])
        {
            a[t] = b[r];
            r++;
        }
        else
        {
            a[t] = c[s];
            s++;
        }
        t++;
    }
    if (r==q)
    {
        while(s!=p)
        {
            a[t] = c[s];
            s++;
            t++;
        }
    }
    else
    {
        while(r != q)
        {
            a[t] = b[r];
            r++;
            t++;
        }
    }
    return;
}