使用数组进行合并排序的空间复杂度

Question

这个算法是mergesort,我知道这可能看起来很奇怪,但我主要关注的是计算这个算法的空间复杂度.

如果我们查看mergesort函数的递归树并尝试跟踪算法,那么堆栈大小将是log(n).但由于merge功能也有内部的mergesort,其产生的大小两个数组n/2,n/2,那么首先应该我觉得递推关系的空间复杂度,然后,我要补充的是中n/2 + n/2,这将成为O(log(n) + n).

我知道答案,但我在这个过程中感到困惑.谁能告诉我正确的程序？

这种混淆是由于合并函数,它不是递归的,而是在递归函数中调用

为什么我们说空间复杂性将O(log(n) + n)通过递归函数空间复杂度的定义,我们通常计算递归树的高度

Merge(Leftarray, Rightarray, Array) {
    nL <- length(Leftarray)
    nR <- length(Rightarray)
    i <- j <- k <- 0
    while (i < nL && j < nR) {
        if (Leftarray[i] <= Rightarray[j])
            Array[k++] <- Leftarray[i++]
        else
            Array[k++] <- Rightarray[j++]
    }
    while (i < nL) {
        Array[k++] <- Leftarray[i++]
    }
    while (j < nR) {
        Array[k++] <- Rightarray[j++]
    }    
}  

Mergesort(Array) {
    n <- length(Array)
    if (n < 2)
        return
    mid <- n / 2
    Leftarray <- array of size (mid)
    Rightarray <- array of size (n-mid)
    for i <- 0 to mid-1
        Leftarray[i] <- Array[i]
    for i <- mid to n-1
        Right[i-mid] <- Array[mid]
    Mergesort(Leftarray)
    Mergesort(Rightarray)
    Merge(Leftarray, Rightarray) 
}    

Answer 1

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) => 空间复杂度为 O(nlogn + n) = O(nlogn)。但是，实际代码中并非如此，因为它不是并行执行的。例如，在 N = 16 的情况下，归并排序的代码就是这样执行的。N = 16。

                       16
                      /
                     8
                    /
                   4
                 /
                2
               / \
              1   1

注意使用的空间数是 32 = 2n = 2*16 < 3n

然后向上合并

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

即 34 < 3n。然后向上合并

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

36 < 16 * 3 = 48

然后向上合并

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

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

在更大的情况下，n = 64

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

即 64*3 <= 3*n = 3*64

您可以通过对一般情况的归纳来证明这一点。

因此，空间复杂度总是以 O(3n) = O(n) 为界，即使您使用数组实现，只要您在合并后清理使用的空间并且不是并行执行代码而是按顺序执行代码。

我的实现示例如下：