这两个mergesort实现的空间复杂度是否相同? [英] Is the space complexity for these 2 mergesort implementations the same?

问题描述

你好，我想告诉我这两种mergesort算法的空间复杂度是否相同.

Hello I would like you to tell me if the space complexity for those 2 mergesort algorithms is the same.

算法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调用而被推入堆栈的.

Intuitively for me Algo2 has a worse space complexity since the copied lists lefthalf and righthalf get pushed into the stack with the mergeSort2 calling them.

Algo1直到合并时间temp_list = [None]*(r-l+1)才分配额外的空间，因此执行堆栈仅具有当前执行的mergeSort的额外数组.

Whereas Algo1 does not allocate extra space until the time to merge comes temp_list = [None]*(r-l+1) , so the execution stack has only the extra array for the mergeSort currently being executed.

这是正确的吗?

推荐答案

首先，让我们假设我们拥有完善的垃圾收集功能，并且每个列表在不使用后都会立即释放.

First, let's assume that we have perfect garbage collection and every list is deallocated immediately after it falls out of use.

在这种假设下，算法具有相同的大O空间复杂度.

With this assumption, the algorithms have the same big O space complexity.

首先看一下算法2并考虑以下示例: 想象一下，您正在对长度为16的列表进行排序.

Take a look at Algorithm 2 first and consider the following example: Imagine you're sorting a list of length 16.

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

您计算列表的前一半和后一半:

You compute the first and the second half of the list:

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

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

Then you sort the first half, in particular you divide it into two new sublists:

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

然后您再次执行相同操作:

And you do the same again:

[15,14]  [13,12]

再次:

[15]  [14]

然后，您才开始合并列表.

Only then you begin to merge the lists.

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

是16 + 2*8 + 2*4 + 2*2 + 2*1.通常，它是N + 2N/2 + 2N/4 + 2N/8 + ... + 2.这是一个简单的几何级数，总计约为3 * N.

It is 16 + 2*8 + 2*4 + 2*2 + 2*1. In general, it's N + 2N/2 + 2N/4 + 2N/8 + ... + 2. That's a simple geometric progression that sums to something around 3*N.

该算法还需要O(log(N))空间用于调用堆栈，但是以大的O表示法消失了: O(N)

The algorithm also needs O(log(N)) space for the call stack, but that vanishes in the big O notation: O(N)

很容易看出这是算法在任何给定点将使用的最大值-将来将要使用的分配列表的长度(因此不能被释放)不会超过3 * N.

It is easy to see that this is the maximum of what the algorithm will use at any given point -- the length of allocated lists that will be used in the future (and cannot be deallocated because of that) will never exceed 3*N.

再次考虑相同的示例.我们将对以下列表进行排序.

Consider the same example again. We're to sort the following list.

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

想象一下，我们已经对其前半部分和后半部分进行了排序:

Imagine that we have already sorted its first and second half:

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

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

Now, we need to allocate a temporary list of length N to perform the merge. So at that moment we actively use two lists of length N, that gives us 2*N = O(N).

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

Again, it is easy to see that we'll never use more memory: the task of sorting the halves of the list naturally cannot cost more than sorting the list itself.

这两种算法都使用 O(N)内存.他们将O(log(N))用于调用堆栈，但是与O(N)相比，这是一笔不小的开销.

Both algorithms use O(N) memory. They use O(log(N)) for the call stack, but that's a minor expense compared to O(N).

另外知道 Python使用引用计数取消分配未使用的对象可验证我们的初始垃圾收集的假设.

Knowing additionally that Python uses reference counting to deallocate unused objects validates our initial assumption about garbage collection.

这篇关于这两个mergesort实现的空间复杂度是否相同?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！