Big O Zeit in oprator in Python läuft

Question

Ich frage mich, was ist die große O Zeit des unter einfaches Programm ausgeführt wird:

dates = [0,2,3,4] 
sample_list = [1,2,3,4] 
for i in range(0, 4): 
    sub_list = sample_list[i+1:] 
    if dates[i] in sub_list: 
     count += 1 

Ist die Laufzeit O(n) oder O(n**2)? Ich weiß, die Laufzeit ist mindestens O(n), weil ich eine for-Schleife habe, aber wie wäre es mit der if dates[i] in sub_list-Anweisung? Was ist die Laufzeit dafür?

Answer 1

Ihre Schleife scheint nicht von der Länge Ihrer Liste (n) zu abhängen, obwohl es wahrscheinlich sollte. Der Aufruf an sample_list[i+1:] hängt jedoch von der Größe sample_list sowie dates[i] in sub_list ab.

Aus diesem Grund ist Ihr Code O(n), wobei n die Länge sample_list ist.