python - 在 python : slicing vs iterating - impact on complexity 中合并排序

Question

我想检查一下我对 python 如何处理切片的理解是否正确。

这是我对归并排序的实现:

def merge_sort(L):
    def merge(a, b):
        i, j = 0, 0
        c = []
        while i < len(a) and j < len(b):
            if a[i] < b[j]:
                c.append(a[i])
                i += 1
            elif b[j] < a[i]:
                c.append(b[j])
                j += 1
        if a[i:]:
            c.extend(a[i:])
        if b[j:]:
            c.extend(b[j:])
        return c

    if len(L) <= 1:
        return L
    else:
        mid = len(L) // 2
        left = merge_sort(L[:mid])
        right = merge_sort(L[mid:])
        return merge(left, right)

我认为我可以替换它是否正确:

if a[i:]:
    c.extend(a[i:])
if b[j:]:
    c.extend(b[j:])

有了这个:

while i < len(a):
    c.append(a[i])
    i += 1
while j < len(b):
    c.append(b[j])
    j += 1

并且具有完全相同的复杂程度？我对切片的理解是它的复杂度等于切片长度？对吗？

我调用切片两次(第一次在条件中，第二次在其中)是否使它的复杂度增加了 2 倍？

Answer 1

您对 mergesort 的实现有问题:

• 在merge函数的主循环，如果 a[i] 中的值，则什么都不做和 b[j]是相等的，或者更准确地说，如果你没有 a[i] < b[i]也不a[i] > b[i] .这会导致无限循环。
• 不需要定义merge作为局部函数，其实没有必要做成一个单独的函数，可以内联代码，节省函数调用的开销。

修改后的版本:

def merge_sort(L):
    if len(L) <= 1:
        return L
    else:
        mid = len(L) // 2
        a = merge_sort(L[:mid])
        b = merge_sort(L[mid:])
        i, j = 0, 0
        c = []
        while i < len(a) and j < len(b):
            if a[i] <= b[j]:
                c.append(a[i])
                i += 1
            else:
                c.append(b[j])
                j += 1
        if a[i:]:
            c.extend(a[i:])
        else:
            c.extend(b[j:])
        return c

关于性能，切片或迭代对复杂性没有影响，因为这两种操作都具有线性时间成本。

关于性能，这里有尝试的方向:

• 替换测试if a[i:]与 if i < len(a) .两次创建切片的成本很高。
• 执行就地排序，避免 append运营
• 重构主循环，使每次迭代只有一个测试

修改后的版本:

def merge_sort(L):
    if len(L) <= 1:
        return L
    else:
        mid = len(L) // 2
        a = merge_sort(L[:mid])
        b = merge_sort(L[mid:])
        i, j, k = 0, 0, 0
        while True:
            if a[i] <= b[j]:
                L[k] = a[i]
                k += 1
                i += 1
                if (i == len(a)):
                    L[k:] = b[j:]
                    return L
            else:
                L[k] = b[j]
                k += 1
                j += 1
                if (j == len(b)):
                    L[k:] = a[i:]
                    return L