Quadratische Zeitkomplexität: Warum wird der folgende Code auf diese Weise berechnet?

Question

Könnte jemand bitte erklären, warum die folgende Code-Komplexität auf diese Weise berechnet wird: 1 + 2 + 3 + 4 + ... + (n-2) + (n-1) + n = 0 (n^2)

def CalculateAveragesTotElementOverzicht(inputlist): 
    resultlist = [0]*len(inputlist) 
    for i in range(0,len(inputlist)): 
     som = 0 
     for j in range(0,i+1): 
      som += inputlist[j] 
     average = som/(i+1) 
     resultlist[i] = average 
    return resultlist 

Answer 1

Es ist nicht O(n) aber O (n). Und das ist, weil Sie zwei Schleifen, die die äußere Iterierten 0-n und die innere aus 0 zum Wegwerf-Variablen Größe (i), die in jeder Iteration generiert es die folgenden Bereiche:

range(0,0+1) # 1 iteration 
range(0,1+1) # 2 iteration 
range(0,2+1) # 3 iteration 
    ... 

daher bei das Ende, müssen Sie 1 + 2 + 3 + ... + n Iteration, die die Komplexität als fllows berechnet:

n * (n + 1)/2 = 1/2 n 2 + 1/2n = 0 (n)