時間複雑

Question

は、誰かが次のコードの時間計算を支援することができます計算：最初のループの実行をn回になる私には

for(i = 0; i <= n; i++) 
{ 
    for(j = 0; j <= i; j++) 
     { 
     for(k = 2; k <= n; k = k^2) 
       print("") 
     } 

/C、第二は、（1 + 2 + 3のために実行されます。 ..n）回とloglogn回のための3番目.. しかし、答えについてはわからない。

Answer 1

内部から作業を開始します。 print("")の反復が実行されているどのように多くの

for(k = 2; k <= n; k = k^2) 
    print("") 

：最も内側のループを考えてみましょうか？最初は、nが一定であることに注意してください。 kはどのような値のシーケンスを想定していますか？

iter | k 
-------- 
    1 | 2 
    2 | 4 
    3 | 16 
    4 | 256 

いくつかの点で、数式が見つかります。私は推測を使用してiter = log(log(k)) + 1を得ることを証明します。値がすでにnより大きい場合、ループは次の反復を実行しないため、nに対して実行された反復の合計数はfloor(log(log(n)) + 1)です。これを確認するためにいくつかの値を付けて確認することができます。 n = 2については、正しい1回の反復が得られます。 n = 5については、2つを取得します。等々。

次のレベルはi + 1回です。ここで、iは0からnまで変化します。したがって、合計1, 2, ..., n + 1を計算する必要があります。これは、最外ループと中間ループの合計反復回数を返します。この合計は(n + 1)(n + 2)/2です。内部ループのコストを乗算して合計コストを得るには、(n + 1)(n + 2)(log(log(n)) + 1)/2を計算する必要がありますスニペットの展開の中で最も急成長している用語はn^2 log(log(n))であり、一般的に漸近的な複雑さとして与えられるものである。