0

Big O表記を使用してforループの複雑さを理解しようとしています。以前に他のクラスでこれを行ったことがありますが、これは実際のアルゴリズムに基づいているため、他のクラスよりも厳密です。コードは次のとおりです。

for(i=n ; i>1 ; i/=2) //for any size n
{
    for(j = 1; j < i; j++)
    {
      x+=a
    }
}

命令 x+=a は合計 n + n/2 + n/4 + ... + 1 回実行されます。

開始項 n と公比 1/2 を持つ GP の最初の log2n 項の合計は、(n (1-(1/2)log2n))/(1/2) です。したがって、最初のコード フラグメントの複雑さは O(n) です。

正しい ？

4

1 に答える 1

3

はい。それで合っています。ただし、次の理由から、対数を含める必要はありません。

n + n/2 + n/4 + ... + 1 = 2*n - 1

(この方程式は 2 の累乗である n に対して正確であり、2 の累乗でない場合はわずかにずれています)

更新：証明。

私たちの和を呼びましょうx：

x = n + n/2 + n/4 + ... + 1

また、簡単にするために、n は 2 の累乗であると仮定します。したがって、すべての要素は 2 の累乗で割り切れ、剰余はありません。

を掛けるxと2、非常に興味深いことがわかります。

2*x = 2*n + 2*(n/2) + 2*(n/4) + ... + 2

または、これを次のように書き換えることができます。

2*x = 2*n + x - 1

次のように簡略化できます。

x = 2*n - 1
于 2013-06-02T22:45:26.140 に答える