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

Question

让我们以合并排序的实现为例

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（nlg（n））。并行化（1）和（2）会带来实际收益吗？从理论上讲，在对它们进行并行化之后，似乎最终也会出现O（nlg（n））。但实际上我们能得到什么好处吗？

b） 这种合并排序的空间复杂度是O（n）。但是，如果我选择使用链表执行就地合并排序（不确定是否可以合理地使用数组），空间复杂性是否会变得O（lg（n）），因为您必须考虑递归堆栈帧大小？既然它不能超过64，我们能把O（lg（n））当作常数吗？我可能在几个地方误解了这一点。64的意义到底是什么？

c） 比较排序算法-c编程。com说合并排序需要使用链表的恒定空间。怎样他们是否对待O（lg（n））常数？

d） 添加以获得更清晰的信息。对于空间复杂度计算，假设输入数组或列表已经在内存中是否公平？当我进行复杂度计算时，除了输入已经占用的空间外，我总是计算我将需要的“额外”空间。否则，空间复杂度将总是O（n）或更糟。

Answer 1

a） 当然，并行化合并排序是非常有益的。它仍然是nlogn，但您的常数应该大大降低。

b） 链表的空间复杂度应该是O（n），或者更具体地说是O（n）O（logn）。请注意，这是一个，而不是一个*。做渐近分析时，不要太在意常数。

c） 在渐近分析中，只有方程中的主导项很重要，所以我们有a而不是a*这一事实使它成为O（n）。如果我们复制所有的子列表，我相信这将是O（nlogn）空间——但是基于智能链表的合并排序可以共享列表的区域。

Answer 2

是的——在一个完美的世界里，你必须进行大小为n、n/2、n/4的log n合并......（或者更好地说是1、2、3......n/4、n/2、n——它们不能并行化），这就给出了O（n）...它仍然是O（n log n）。在不那么完美的世界里，你没有无限数量的处理器，上下文切换和同步抵消了任何潜在的收益。

b）空间复杂度总是Ω（n），因为你必须将元素存储在某个地方。额外的空间复杂度可以是使用数组实现中的O（n）和链表实现中的O（1）。在实践中，使用列表的实现需要额外的列表指针空间，所以除非您已经在内存中拥有列表，否则这并不重要。

编辑如果您计算堆栈帧，那么它是O（n）O（logn），所以对于数组仍然是O（n）。在列表的情况下，它是O（logn）额外的内存。

c） 列表只需要在合并过程中更改一些指针。这需要不断增加内存。

d） 这就是为什么在合并排序复杂性分析中，人们会提到“额外的空间需求”之类的东西。很明显，您必须将元素存储在某个地方，但最好提及“额外内存”，以避免纯粹主义者。

Answer 3

MergeSort的时间复杂度是O（nlgn），这是一个基本知识。合并排序空间的复杂度将始终为O（n），包括数组。如果你把空间树画出来，看起来空间复杂度是O（nlgn）。但是，由于该代码是深度优先的代码，您将始终只沿着树的一个分支进行扩展，因此，所需的总空间使用量将始终以O（3n）=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）=

                           16
                          /
                         8
                        /
                       4
                     /
                    2
                   / \
                  1   1

请注意，使用的空间数是32=2n=2*16

然后它向上合并

                           16
                          /
                         8
                        /
                       4
                     /  \
                    2    2
                        / \                
                       1   1

哪一个是34

                           16
                          /
                         8
                        / \
                       4   4
                          /
                         2
                        / \ 
                       1   1

36

然后向上合并

                           16
                          / \
                         8  8
                           / \
                          4   4
                             / \
                            2   2
                                /\
                               1  1

16 16 14 = 46

在更大的情况下，n=64

                     64
                    /  \
                   32  32
                       / \
                      16  16
                          / \
                         8  8
                           / \
                          4   4
                             / \
                            2   2
                                /\
                               1  1

也就是64*3

你可以通过归纳法证明这一点。

因此，空间复杂度始终以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
    // http://stackoverflow.com/questions/10342890/merge-sort-time-and-space-complexity/28641693#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;
}

希望这能有所帮助！=）

孙志龙，

多伦多大学