Python函数渐近时间复杂度计算：最小平均切片蛮力法为何为O(N³)

核心错误点：漏算切片操作的时间开销 #

你预估的复杂度和实际不符的核心原因是完全没有计算内层循环中A[i:j+1]切片操作的时间成本，同时你之前的假设有两处错误：

• 假设2错误：curr = sum(A[i:i+1])对应的是长度为1的切片求和，时间复杂度为O(1)，而非你认为的O(N)，这个错误不会导致复杂度升高到三次方。
• 未统计的开销：len(A[i:j+1])中的切片操作A[i:j+1]会生成独立的新子列表，该操作的时间复杂度和切片长度成正比，为O(j - i + 1)。

实际复杂度计算逻辑 #

外层循环共执行N次，对每个i，内层循环执行N-i次，每次内层循环的切片操作成本随j递增线性升高，所有操作的总时间开销总和为O(N³)，和你实际测算的结果一致。

修复方案 #

如果要达到你预期的O(N²)复杂度，只需要将len(A[i:j+1])替换为直接计算长度的表达式j - i + 1即可，不需要生成新的切片：

def min_avg_two_slice(A):
    if len(A) == 2: return 0
    n, idx, min_avg = len(A), None, float('inf')
    for i in range(n):
        curr = A[i]
        for j in range(i+1, n):
            curr += A[j]
            avg = curr / (j - i + 1)
            if avg < min_avg:
                idx = i
                min_avg = avg
    return idx

修复后的代码没有了切片操作的额外开销，时间复杂度即为你最初预估的O(N²)。

内容的提问来源于stack exchange，提问作者23rdpro