我需要一些幫助來理解簡單的複雜性

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)。