这两个合并排序实现的 space 复杂度是否相同？

Question

你好，我想请你告诉我这两个合并排序算法的 space 复杂度是否相同。

算法 1：

def mergeSort(alist, l, r):
    if r - l >= 1:
        mid = l + (r - l)//2

        mergeSort(alist, l, mid)
        mergeSort(alist, mid+1, r)

        i = l
        j = mid+1
        k = 0
        temp_list = [None]*(r-l+1)
        while i < mid+1 and j < r+1:
            if alist[i] <= alist[j]:
                temp_list[k] = alist[i]
                i=i+1
            else:
                temp_list[k] = alist[j]
                j=j+1
            k=k+1

        while i < mid+1:
            temp_list[k] = alist[i]
            i=i+1
            k=k+1

        while j < r+1:
            temp_list[k] = alist[j]
            j=j+1
            k=k+1

        n = 0
        for index in range(l,r+1):
            alist[index] = temp_list[n]
            n += 1

算法 2：

def mergeSort2(alist):
    if len(alist)>1:
        mid = len(alist)//2
        lefthalf = alist[:mid]
        righthalf = alist[mid:]

        mergeSort2(lefthalf)
        mergeSort2(righthalf)

        i=0
        j=0
        k=0
        while i < len(lefthalf) and j < len(righthalf):
            if lefthalf[i] <= righthalf[j]:
                alist[k]=lefthalf[i]
                i=i+1
            else:
                alist[k]=righthalf[j]
                j=j+1
            k=k+1

        while i < len(lefthalf):
            alist[k]=lefthalf[i]
            i=i+1
            k=k+1

        while j < len(righthalf):
            alist[k]=righthalf[j]
            j=j+1
            k=k+1

对我来说，直觉上 Algo2 的复杂性更差 space，因为复制的列表 lefthalf 和 righthalf 被推入堆栈 mergeSort2 调用它们。

而 Algo1 在合并时间 temp_list = [None]*(r-l+1) 之前不会分配额外的 space ，因此执行堆栈只有当前正在执行的 mergeSort 的额外数组。

这是正确的吗？

Answer 1

首先，假设我们有完美的垃圾收集，并且每个列表在不再使用后立即被释放。

根据这个假设，算法具有 相同的大 O space 复杂度。

算法 2

首先看一下算法 2 并考虑以下示例：假设您正在对长度为 16 的列表进行排序。

[15,14,13,12,11,10,9,8,7,6,5,4,3,2,1,0]

您计算列表的前半部分和后半部分：

[15,14,13,12,11,10,9,8]  [7,6,5,4,3,2,1,0]

然后对前半部分进行排序，特别是将其分为两个新的子列表：

[15,14,13,12]  [11,10,9,8]

然后你再做同样的事情：

[15,14]  [13,12]

再一次：

[15]  [14]

然后您才开始合并列表。

此时算法分配的列表总长度是多少？

是16 + 2*8 + 2*4 + 2*2 + 2*1。一般来说，它是N + 2N/2 + 2N/4 + 2N/8 + ... + 2。这是一个简单的几何级数，总和约为 3*N。

该算法还需要 O(log(N)) space 用于调用堆栈，但这在大 O 表示法中消失了：O(N)

很容易看出，这是算法在任何给定点将使用的最大值——将来将使用的已分配列表的长度（因此无法取消分配）永远不会超过 3*N.

算法 1

再次考虑同一个例子。我们要对以下列表进行排序。

[15,14,13,12,11,10,9,8,7,6,5,4,3,2,1,0]

假设我们已经对它的前半部分和后半部分进行了排序：

[8,9,10,11,12,13,14,15, 0,1,2,3,4,5,6,7]

现在，我们需要分配一个长度为N的临时列表来执行合并。所以在那一刻我们积极地使用两个长度为 N 的列表，这给了我们 2*N = O(N).

同样，很容易看出我们永远不会使用更多内存：对列表的两半进行排序的任务自然不会比对列表本身进行排序花费更多。

结论

两种算法都使用 O(N) 内存。他们使用 O(log(N)) 作为调用堆栈，但与 O(N) 相比，这是一个很小的开销。

另外知道 Python uses reference counting 释放未使用的对象验证了我们关于垃圾收集的初始假设。

这两个合并排序实现的 space 复杂度是否相同？

Is the space complexity for these 2 mergesort implementations the same?

python

sorting

algorithm

mergesort

算法 2

算法 1

结论