Является ли сложность времени этой реализации сортировки слиянием O (nlogn)? - PullRequest
Новая
       108

Является ли сложность времени этой реализации сортировки слиянием O (nlogn)?

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

В этом онлайн-учебнике https://runestone.academy/runestone/static/pythonds/SortSearch/TheMergeSort.html они дают следующий код для слияния: 

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

        mergeSort(lefthalf)
        mergeSort(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

В анализе онлайн-книга заставляет писать:

Напомнимчто оператором среза является O (k), где k - размер среза.Чтобы гарантировать, что mergeSort будет иметь значение O (nlogn), нам нужно будет удалить оператор слайса. Опять же, это возможно, если мы просто передадим начальный и конечный индексы вместе со списком при выполнении рекурсивного вызова.

Итак, мой первый вопрос:

1- Можете ли вы, ребята, рассказать мне о сценарии, в котором операторы срезов разрушат временную сложность алгоритма?

Я написал кодчтобы сделать это без операции среза ниже: 

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

        mergeSort2(alist, l, mid)
        mergeSort2(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:

2- Как я понимаю, вместо того, чтобы делать 2 среза, которые занимают k время перед рекурсивными вызовами, мы теперь инициализируем temp_list за k время и затем копируем отсортированный temp_list в наш результат в k времяЗначит, временная сложность алгоритма не изменилась?

1 Ответ

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

Нарезка не должна влиять на сложность времени с точки зрения его порядка.Постоянный фактор - другое обсуждение.

Ключевая часть понимания того, как сложность времени неизменна, здесь: 

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

        mergeSort(lefthalf)
        mergeSort(righthalf)

Итак, давайте разберем ее шаг за шагом:

Здесь мы копируем весь список,Это O(N) 

lefthalf = alist[:mid]
righthalf = alist[mid:]

Эта часть вызывает mergeSort слева и справа, что приводит к рекурсивному разрезанию.

mergeSort(lefthalf)
mergeSort(righthalf)

mergeSort(lefthalf) и mergeSort(righthalf) вместе срезают весь массив, и сумма их рекурсивных потомков будет делать то же самое.Дело в том, что количество раз, когда массив будет разрезан целиком, равно log N, поскольку вы продолжаете делить массив на 2, и вы можете сделать это только log N раз.Это дает вам O(N) раз срезов O(log N) раз, когда вы делаете срез, в результате чего O(NlogN)

Суммируется:

  1. Нет, если срезы реализованы правильно.Очевидно, вы можете добавить случайные кусочки и испортить сложность времени.

  2. Нарезка не изменит масштаб сложности вашего времени - все же O(NlogN)

...