如何计算 python 函数的时间复杂度（渐近表示法）？

Question

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 = sum(A[i:i+1])
        for j in range(i+1, n):
            curr += A[j]
            avg = curr / len(A[i:j+1])
            if avg < min_avg:
                idx = i
                min_avg = avg
    return idx

Codility 在前缀和下有问题，它是一个具有最小平均切片的子序列。上面的解决方案是蛮力的，希望得到二次时间，但是，我得到了 O(N**3) ，它是三次方的。

假设

内部循环应该是== O(N)
curr = sum(A[i:i+1]) == O(N)
外循环和另外两个循环变成 O(N (N + N)) == O(N (2N)) == O(N(N)) == O(N**2)

我的问题是，这个假设是错误的还是缺少复杂性？谢谢。

Answer 1

当你这样做时

len(A[i:j+1])

您正在创建切片 A[i:j+1]。创建切片的时间复杂度为 O(n)（其中 n 是切片的长度）。这会增加程序的复杂性。

由于你只使用切片作为长度，所以你根本不需要在这里创建切片：切片的长度是(j+1-i)，所以你可以直接使用它。

如何计算 python 函数的时间复杂度（渐近表示法）？

How to calculate time complexities for python functions (asymptotic notation)?

python

big-o

complexity-theory