j <= iのネストされたforループの時間複雑度

Question

私は割り当てに関してこの質問をしました。

私はiとjは、複雑さはLOG2（N）* LOG2（N）の線に沿って何かだろうと2倍ずつ増加しているとのことを理解し

for(int i=1; i<=n; i=2*i){ 
    for(int j=1; j<=i; i=2*j){ 
     stuff 
    } 
} 

ネストされたループの時間複雑性を決定します私は完全に失われています。

ネストされたループの複雑さと、それがどのように解決されたかを段階的に把握する必要があります。

Answer 1

内部ループはlog(i) + 1回（ベース2ログ）を実行します。外側のループの追加

は、i = 1, 2, 4, ... nについて上記を合計します。だから、

：ある(log(1) + 1) + (log(2) + 1) + (log(4) + 1) + ... + (log(n) + 1)

：1 + 2 + 3 + ... + log(n)

算術級数の和を用いている：(log(n) + 1) * (log(n) + 2)/2 = (log(n)*log(n) + 3log(n) + 2)/2 = O(log(n) * log(n))

Answer 2

はのは、例えば16を想定し、N =ましょう、私は値i = 1, 2, 4, 8, 16を持つことになります。

So：私は基本的にlog（n）すなわちlog（16）すなわち5回の反復として値を取っています。

ここでjの値は、log(1) + log(2) + log(4) + log(8) + log(16)となります。これは基本的に各繰り返しでlog（i）に等しいです。

だから我々は、上記の二つの文から得た値を組み合わせることで、我々は、上記のコードの時間複雑性はO(log(n) * log(i))であると言うことができます。

これはコードに関する私の理解です。