python - 这个mergesort实现的时间复杂度是O(nlogn)吗？

Question

在这本在线教科书中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

在在线书籍的分析中，他们写道:

Recall that the slicing operator is O(k) where k is the size of the slice. In order to guarantee that mergeSort will be O(nlogn) we will need to remove the slice operator.Again, this is possible if we simply pass the starting and ending indices along with the list when we make the recursive call.

所以我的第一个问题是:

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 个需要 k 时间的切片，我们现在正在 k 中初始化 temp_list > 时间，然后在 k 时间内将排序后的 temp_list 复制到我们的结果中。那么算法的时间复杂度没有变？

Answer 1

就数量级而言，切片根本不应该影响时间复杂度。常数因子是另一个讨论。

理解时间复杂度如何不变的关键部分在这里:

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)