Одинакова ли сложность пространства для этих двух реализаций слияния?

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 использует подсчет ссылок для освобождения неиспользуемых объектов, проверяетнаше первоначальное предположение о сборке мусора.