为什么这个奇怪的执行时间

Question

我正在使用这个排序算法：

def merge(L,R):
    """Merge 2 sorted lists provided as input
    into a single sorted list
    """
    M = [] #Merged list, initially empty
    indL,indR = 0,0 #start indices
    nL,nR = len(L),len(R)

    #Add one element to M per iteration until an entire sublist
    #has been added
    for i in range(nL+nR):
        if L[indL]<R[indR]:
            M.append(L[indL])
            indL = indL + 1
            if indL>=nL:
                M.extend(R[indR:])
                break
        else:
            M.append(R[indR])
            indR = indR + 1
            if indR>=nR:
                M.extend(L[indL:])
                break
    return M

def func(L_all):

    if len(L_all)==1:
        return L_all[0] 
    else:
        L_all[-1] = merge(L_all[-2],L_all.pop())
        return func(L_all)

merge() 是经典的合并算法，其中，给定两个排序数字列表，它将它们合并为一个排序列表，它具有线性复杂度。输入的一个例子是 L_all = [[1,3],[2,4],[6,7]]，一个包含 N 个排序列表的列表。该算法对列表的最后一个元素应用合并，直到列表中只有一个元素被排序。我已经评估了不同 N 的执行时间，对列表中的列表使用恒定长度，我得到了一个意想不到的模式。该算法具有线性复杂度，但执行时间是常数，如图所示

执行时间不依赖于 N 的原因是什么？

Answer 1

您还没有显示您的时间代码，但问题很可能是您的 func 突变列表 L_all 使其成为长度为 1 的列表，包含单个排序列表。在 timeit 中第一次调用 func(L_all) 后，所有后续调用都不会改变 L_all。相反，他们只是立即 return L_all[0]。而不是对 timeit 中的每个 N 调用 L_all 100000 次，你实际上只是对每个 N 进行一个真正的调用.您的计时代码仅显示 return L_all[0] 是 O(1)，这不足为奇。

我会这样重写你的代码：

import functools, random, timeit

def func(L_all):
    return functools.reduce(merge,L_all)

for n in range(1,10):
    L = [sorted([random.randint(1,10) for _ in range(5)]) for _ in range(n)]
    print(timeit.timeit("func(L)",globals=globals()))

那么即使对于这些小的 n 你也会看到对 n 的明显依赖：

0.16632885999999997
1.711736347
3.5761923199999996
6.058960655
8.796722217
15.112843280999996
17.723825805000004
22.803739991999997
26.114925834000005

为什么这个奇怪的执行时间

Why this strange execution time

python

time

time-complexity