这个 for 循环的时间复杂度是多少？

Question

for i in range(n - length + 1):
     minimumvalue = min(diskSpace[i:i + length])
     minimumList.insert(len(minimumList), minimumValue)

return(max(minimumArray)

因此，对于 i in range 需要 O(n) 时间，python 最小函数是 O(n) 时间，插入是 0(n) 时间。由于这些在我的 for 循环中，我的总时间复杂度是 O(n^2) 还是 O(n)？

Answer 1

它是 O(n)，因为您对 min() 和 insert() 函数的复杂性的理解是错误的。

min() 通常是 O(n)，但您总是使用相同的 length 元素来调用它。除非 length 依赖于 n，否则可以将其视为常数时间。

insert() 通常也是 O(n)，但您通过指定位置 len(minimumList) 在末尾插入，因此这是摊销常数时间。其实在那个位置插入相当于minimumList.append(minimumValue)，就是摊销常数时间

代码中唯一依赖n的部分是for i in range(n - length + 1):

的迭代次数

如果length是复杂度的输入，那么总的复杂度是O(n*length)。

Answer 2

min 函数是 O(n)，因为它是每个元素的恒定操作量（n * 某个常数）。您的 for 循环为每个元素执行此操作 (n * (some constant * n)).

所以那将是 n * n（我们可以省略常量，因为这对于查看此函数的缩放程度并不重要），因此您的运行时间为 O(n^2)。

这个 for 循环的时间复杂度是多少？

What is the time-complexity of this for-loop?

python

time

complexity-theory

for-loop

list