python - 使用内置函数的这个函数的时间复杂度是多少？

Question

假设您有以下compute函数，使用 python 内置sum函数：

def compute(a_list):
    for i in range(0, n):                        #Line 1
        number = sum(a_list[0:i + 1])/(i+1)      #Line 2
    return number

像这样的事情的时间复杂度是什么样的？

Line 1执行 n 次，但是Line 2，具有内置sum函数 (O(n))，它会执行 n^2 次吗？因此算法将是 O(n^2)。

对于 i 的每次迭代，Line 2执行 1 + 2 + 3 + ... + n-2 + n-1 + n。这些项的总和是

这个对吗？

标签： pythontime-complexity

Answer 1

我会说第 1 行执行一次，这会导致第 2 行执行n多次。列表下标是O(n)，sum也是O(n)。除法，加法和赋值都是O（1）。

compute因此是 O(N^2)，因为最大的项正在评估 O(n) 操作 O(n) 次。

请注意，正如所写，它会丢弃所有中间结果，因此可以将其重写为：

def compute(a_list):
    return sum(a_list[0:n])/n

这将是 O(n)。