whileループを含むアルゴリズムの分析

Question

アルゴリズムの分析時には、通常for loopの問題はありませんが、while loopを含むアルゴリズムの実行時間の分析には問題があります。私は私の質問を表現するための例を示します。

次一つは、私が今勉強coin-change algorithm（私たちのほとんどのためのよく知られたアルゴリズム）の一部です：

counter = 0 
s = 0 
while(s <= n/100) 
    s = s+1 
    t1 = n- 100*s 
    h = 0 
    while(h <= t1/50) 
      h = h +1 
      t2 = t1 - 50*h 

... 

誰かがそのようなの走行時間を知る最良の方法を説明することができますWhileループ中にネストされたアルゴリズム？

Answer 1

whileループはforループを書くもう1つの方法です。そのため、複雑さを評価することは異なるものであってはなりません。ここ

は、アウターwhileループが各反復について1によってs増加するので（現実の世界ではnに比例する）複雑さの世界でn回実行し、sがnに比例した値に達するまで、それが実行されます。

少し混乱していると思われる内側のループは、t1回（やはり複雑な世界）どこでもt1 = n - 100sです。今度は、アルゴリズムがO（n^2）だと思っていますが、各繰り返しでt1が減少するので、内側のループは後続の繰り返しごとに実行回数が少なくなり、O（n^2）ではなくなります。

t1は、繰り返しごとに異なるため、反復のセット全体はn - 100 + n - 200 + n - 300 + .... 0回実行されます。この系列の項の数はnに比例するので、総和はn乗の項を持ち、複雑さを報告するためにはすべての下位項は無視され、残りの数字の合計について心配する必要はありません。このアルゴリズムはO（n^2）です。

トリックは、各ステップで定数と下位の項を無視して簡単になります！