Ich brauche etwas Hilfe, einfache Komplexität zu verstehen

Question

Kann jemand erklären, wie quadratisch v2 ist eine quadratische und andere kleine Details, die in den anderen Funktionen wichtig sein könnten? Ich dachte, dass die Variable, die durchlaufen wurde, zweimal aufgerufen werden musste, damit sie quadratisch war.

def linear(L): 
    index = 0 
    while index < len(L): 
    index = index + 1 

def linear_v2(L): 
    index1 = 0 
    while index1 < len(L): 
    index2 = 0 
    while index2 < 1000000: 
     index2 += 1 
    index1 += 1 

def quadratic(L): 
    index1 = 0 
    while index1 < len(L): 
    index2 = 0 
    while index2 < len(L): 
     index2 += 1 
    index1 += 1 

def quadratic_v2(L): 
    index1 = 0 
    while index1 < len(L): 
    index2 = 0 
    while index2 < index1: 
     index2 += 1 
    index1 += 1 


def cubic(L): 
    index = 0 
    while index < len(L): 
    index2 = 0 
    while index2 < len(L): 
     index3 = 0 
     while index3 < len(L): 
      index3 += 1 
     index2 += 1 
    index +=1 

def log(L): 
    index = 0 
    while 2 ** index < len(L): 
    index += 1 

def exponential(L): 
    index = 0 
    while index < 2 ** len(L): 
    index +=1 

Answer 1

quadratic_v2 quadratisch ist, da der Inhalt der inneren Schleife noch im quadratischen Verhältnis zu der Länge von L. Der Koeffizient ausführt kleiner ist als in der Funktion quadratic aber es ist dennoch quadratisch.

Sie können sich vorstellen, dass, wenn wir die Länge von L erhöhen, zwei Schleifen betroffen sind. Sowohl der äußere als auch der innere. Der innere ist weniger betroffen als mit quadratic aber es ist immer noch, seit index1 wird größer.

Der Inhalt der inneren Schleife in quadratic_v2 wird, für die Länge L n, in der ersten Schleife der äußeren Schleife 1 Mal aufgerufen werden, in der zweiten Schleife der äußeren Schleife 2 mal usw. Alle Anrufe werden dann:

1 + 2 + 3 + ... + n 

Wir können diese Summe schreiben auch als n * (n + 1)/2, die 1/2 n^2 + 1/2n gleich ist. Dies bedeutet, dass die Funktion O(n^2) lautet.