algorithm - ループ反復分析

Question

以下の解決策を参照してください。建設的なフィードバックをお願いします。

以下のO（n）での実行時間はどれくらいですか。

int a = 0;
int k = n*n*n; //n^3
while(k > 1) 
{
  for (int j=0; j<k; j++) //runs from 0->k
  { a--; }
k = k/2; //divides by 2 each iteration
}

forループが実行されるたびに、定数xkが得られます。

= 0xn ^ 3 + 1x（n ^ 3/2）+ 2x（n ^ 3/4）+ ... + nx（n ^ 3/2 ^ n）
= n ^ 3（0 + 1/2 + 2 / 4 + ... + n / 2 ^ n）<-これをさらに単純化する方法を知っている人はいますか？

編集：私はどういうわけか算術級数を使用すると仮定しています...。

Answer 1

最初にkを使用しましょう

最初のwhileループでは、forループはk回実行されます

2番目のwhileループでは、forループはk/2回実行されます

3番目のwhileループでは、forループはk/4回実行されます

..。

したがって、合計で（k + k / 2 + k / 4 + k / 8 + ... + 1）回実行されます

kを抽出した後、それはk *（1 + 1/2 + 1/4 + 1/8 + ... + 1 / k）

kが増加すると、括弧内の部分は2になりますが、これは無視できます。

kをn^3に変更すると、結果はO（n ^ 3）になります。

Answer 2

以下の正式な方程式を使用して、成長の複雑さの順序を考え出すことができると思います。