Python: for 循环内 min() 函数的时间复杂度

Question

我正在计算算法的时间复杂度，我假设下面的两个代码都具有 O(n^2) 的时间复杂度但是我的书说第一个代码是 O(n^2)，第二个是 O(n)。我不明白为什么。两者都使用min/max，有什么区别？代码 1:

def sum(l, n):

for i in range(1, n - 1):
    x = min(l[0:i])
    y = min(l[i:num])
return x+y

代码 2：

def sum(a, n):
r = [0] * n
l = [0] * n
min_el = a[0]

for i in range(n):
    min_el = min(min_el, a[i])
    l[i] = min_el


print(min_el)

Answer 1

在第一个代码块中，该代码块对整个数组运行 min 函数，这需要 O(n) 时间。现在考虑它在一个长度为 n 的循环中，那么总时间是 O(n^2)

查看第二个代码块。请注意，min 函数仅比较 2 个值，这可以说是 O(1)。现在考虑它在一个长度为 n 的循环中。总时间只是O(n+n+n)的总和，等于O(n)

Answer 2

在第一段代码中，它给了一个数组给min()函数，这个O(n)的时间复杂度是因为它检查了数组中的所有元素，在第二段代码中，min()函数只比较了两个值，它需要 O(1)

Python: Time complexity of min() function inside for loop