この関数のアルゴリズムの複雑さ

Question

def mystery(L): 

sum1 = 0 
sum2 = 0 
bound = 1 
while bound <= len(L): 
    i = 0 
    while i < bound: 
     j = 0 
     while j < len(L): 
      if L[j] > L[i]: 
       sum1 = sum1 + L[j] 
      j = j + 2 
     j = 1 
     while j < len(L): 
      sum2 = sum2 + L[j] 
      j = j*2 
     i = i + 1 

    bound = bound * 2 
return sum1 + sum2 

この関数の複雑さはわかりません。私は私のループに行って、何をすべきか分からない。

Answer 1

中間レベルのwhileループが何回実行されているかを分かりやすくするのはちょっと難しいことです。外側ループは、各パス（len(L)まで）で2分の1になるようにboundを増やします。つまり、iループは、パス（Nはlen(L)）のパスあたりO(bound)回実行されます。問題は、パスごとに変更されるため、boundの値をどのように加算するかです。

合計を計算する最も簡単な方法は、ループが終了する直前に最大のboundから開始することです。まず、N（別名len(L)）が2の累乗であると仮定してください。最後のboundの値は、正確にはNに等しくなります。次に小さいもの（最後の反復の次に使用される）はN/2となり、それ以降はN/4となります。それらの合計は次のようになります。

N + N/2 + N/4 + N/8 + ... + 1 

我々は、各タームからNを考慮した場合、我々は得るでしょう：

N*(1 + 1/2 + 1/4 + 1/8 + ... + 1/N) 

あなたは括弧内に合計を認識しなければならない、それは単純な幾何学シリーズ（合計です1/2の力の）、それは数学と分析でかなり頻繁に現れます。合計が永遠に続く場合は、それは正確に2に加算されます。私たちは少し早く辞めるので、それは最後の期間（1/N）に等しい金額で2以下になります。我々は再びでN用語を掛けるとき、私たちは2*N - 1回実行されるように全部を取得し、そのループは、O(N)

Nが正確に2のべき乗ではありません同じビッグ-Oバウンドな作品である値から、我々上記の分析で合計された値は、ループ内で実際に表示される値のいずれかの上限になります。

したがって、iループはO(N)回実行されます。