私は単純な複雑さを理解する助けが必要です

Question

2次の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内側ループのコンテンツは、まだ係数が機能quadraticよりも小さいが、それはそれにもかかわらず、二次だL.の長さに二次比例して実行されるので、二次です。

Lの長さを増やすと、2つのループが影響を受けることが想像できます。外側のものと内側のものの両方。内側のものはquadraticより影響を受けませんが、index1が大きくなるので、まだそれがあります。

quadratic_v2における内側ループの含有量は、L Nの長さのために、すべてのコールがされるなど、2回アウターループの第二ループにおいて、外部ループ1回の第1ループに呼び出されますその後：

1 + 2 + 3 + ... + n 

また1/2 n^2 + 1/2nに等しいn * (n + 1)/2として、この合計を書くことができます。つまり、関数はO(n^2)です。