Я написал mergesort 2 различными способами, лучше ли сложность пространства в одном из них по сравнению с другим? - PullRequest
Новая
       19

Я написал mergesort 2 различными способами, лучше ли сложность пространства в одном из них по сравнению с другим?

0 голосов
/ 01 января 2019

В последнее время я практиковал алгоритмы и структуры данных и попал в эту часть https://runestone.academy/runestone/static/pythonds/SortSearch/TheMergeSort.html по слиянию онлайн-книгиВ книге дана реализация алгоритма, и я попытался переписать его, чтобы он занимал меньше места, вот мой код (см. Ссылку на код книги): 

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

        i = l
        j = mid+1
        k = l
       temp_list = alist[:]
       while i < mid+1 and j < r+1:
            if temp_list[i] <= temp_list[j]:
                alist[k] = temp_list[i]
                i=i+1
            else:
                alist[k] = temp_list[j]
                j=j+1
            k=k+1

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

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

Из того, что я читалонлайн космические сложности моей версии и те, которые вы можете найти по этой ссылке https://runestone.academy/runestone/static/pythonds/SortSearch/TheMergeSort.html являются O(n).Если вы делаете это так, как это делается в ссылке, то легко допустить ошибку, предполагая, что сложность пространства равна O(nlogn), но, поскольку все кадры стека не "живы" вместе, это на самом деле O(n) верно?

Моя версия только создает дополнительный список размером n каждый раз, когда мы объединяем, поэтому у меня нет дополнительного места в стеке для хранения левого и правого подсписков.

Так что мои вопросы:

a) Хотя обе версии используют пространство O(n), на самом ли деле моя использует меньше места, чем в книге, по некоторому постоянному коэффициенту или чему-то еще?

b) Как насчет сложности времени?Я не думаю, что это изменилось ... но я новичок в этом, так что, возможно, я облажался.

Спасибо,

d_darric

...