python - 这两个合并排序实现的空间复杂度是否相同？

Question

你好，我想请你告诉我这两种归并排序算法的空间复杂度是否相同。

算法 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 的空间复杂度比复制的列表更差 lefthalf和 righthalf用 mergeSort2 插入堆栈调用他们。

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

这是正确的吗？

Answer 1

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

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

算法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)) 空间用于调用堆栈，但这在大 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释放未使用的对象验证了我们关于垃圾收集的初始假设。