次のコードの時間的複雑度はどのくらいですか？

Question

次のコードの時間の複雑さはどのくらいですか？

a = 2; 
while (a <= n) 
{ 
    for (k=1; k <= n; k++) 
    { 
    b = n; 
    while (b > 1) 
     b = b/2; 
    } 
    a = a * a * a; 
} 

私は外側のwhileループ、loglognあるに苦しんだ、私は理由を理解することはできません。最後の行がa = a * a * a * a;の場合、時間の複雑さはどのように変化しますか？

forループはO(n)、内側はO(logn)です。

したがって合計で、O(n*logn*loglogn)

Answer 1

値は次のようになります。 a = 2 2^3 2^9 2^27 2^81 ... など。

今度は、最後の値は、kは、外側のwhileループの繰り返し回数である2^(3^k)

であると仮定しましょう。簡単にするために

は、最後の行は、時間複雑性は(loglogn)k = log_4(4log_2(n)) = (loglogn)ので、残るa = a * a * a * aた場合のそのa = n^3、そう2^(3^k) = n^3

ので3^k = 3*log_2(n) => k = log_3(3log_2(n)) = (loglogn)

と仮定しましょう。

Answer 2

ループをN回実行され、内側ループは、時間複雑性を有するが、ログはnので、合計時間はO（N Nログ）