Мне нужна помощь в понимании простой сложности

Question

Может ли кто-нибудь объяснить, насколько квадратичный v2 является квадратичным и любые другие мелкие детали, которые могут быть важны в других функциях? Я думал, что переменная, пропущенная, должна была быть вызвана дважды, чтобы она была квадратичной.

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 квадратична, так как содержание внутреннего цикла будет по-прежнему выполняться в квадратичной пропорции к длине L. Коэффициент меньше, чем в функции quadratic но это, тем не менее квадратичной.

Вы можете себе представить, что если мы увеличим длину L, на нее воздействуют две петли. И внешний, и внутренний. Внутренняя часть меньше, чем с quadratic, но она по-прежнему есть, поскольку index1 становится больше.

Содержание внутреннего контура в quadratic_v2 будет, по длине L п, можно назвать в первом контуре внешнего контура 1 раз, во втором контуре внешнего контура 2 раза и т.д. Все вызовы будут затем:

1 + 2 + 3 + ... + n 

Мы можем записать это суммирование и как n * (n + 1)/2, равной 1/2 n^2 + 1/2n. Это означает, что функция O(n^2).