这个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- 我看到它的方式不是在递归调用之前做 2 个切片需要 k 时间我们现在在 k 时间初始化 temp_list 然后复制排序temp_list 到我们的结果在 k 时间。所以算法的时间复杂度没有变？

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)

总结一下：

否如果切片正确实现。显然，您可以添加随机切片并弄乱时间复杂度。
切片不会改变时间复杂度的大小 - 仍然 O(NlogN)

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

Is the time complexity of this mergesort implementation O(nlogn)?

python

algorithm

big-o

mergesort

time-complexity