python 中的合并排序：切片与迭代 - 对复杂性的影响

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

python 中的合并排序：切片与迭代 - 对复杂性的影响

Merge sort in python: slicing vs iterating - impact on complexity

python

mergesort

time-complexity