Квадратичная timecomplexity: почему следующий код рассчитан таким образом?

Question

Может кто-нибудь объяснить, почему следующая сложность кода вычисляется следующим образом: 1 + 2 + 3 + 4 + ... + (n-2) + (n-1) + n = O (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

Это не O(n), но О (п). И это потому, что у вас есть две петли, наружные один перебирает от 0 к n и внутренний один из 0 на холостом размера переменных (i), который в каждой итерации будет генерировать следующие диапазоны:

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

Поэтому в в конце у вас будет 1 + 2 + 3 + ... + n итерация, которую его сложность вычисляет как fllows:

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