algorithm - 使用数组进行归并排序的空间复杂度

问题描述

这个算法是归并排序的，我知道这对你来说可能看起来很奇怪，但我主要关注的是计算这个算法的空间复杂度。

如果我们查看归并排序函数的递归树并尝试跟踪算法，那么堆栈大小将为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) 
}

标签： algorithmtime-complexitybig-omergesort

解决方案

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。

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

然后向上合并

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

36 < 16 * 3 = 48

然后它向上合并

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

在更大的情况下，n = 64

这是 64*3 <= 3*n = 3*64

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

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

我的实现示例如下：

algorithm - 使用数组进行归并排序的空间复杂度

问题描述

解决方案

推荐阅读