Python: Zeitkomplexität der Funktion min() innerhalb der for-Schleife

Ich berechne die Zeitkomplexitäten von Algorithmen und habe angenommen, dass beide folgenden Codes Zeitkomplexitäten von O (n ^ 2) haben. In meinen Büchern heißt es jedoch, dass der erste Code O (n ^ 2) und der zweite O (n) ist. Ich verstehe nicht warum. Beide verwenden Min/Max, also was ist der Unterschied? Code 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

Code 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)

Lösung des Problems

Im ersten Codeblock führt der Codeblock die min-Funktion über das gesamte Array aus, was O(n) Zeit in Anspruch nimmt. Wenn man nun bedenkt, dass es sich in einer Schleife der Länge n befindet, beträgt die Gesamtzeit O (n ^ 2).

Blick auf den 2. Codeblock. Beachten Sie, dass die min-Funktion nur 2 Werte vergleicht, was wohl O (1) ist. Nun bedenke, dass es sich in einer Schleife der Länge n befindet. Die Gesamtzeit ist einfach die Summe von O(n+n+n), was gleich O(n) ist.