このアルゴリズムの時間の複雑さは正しいですか？

Question

私は今、私は、この他のアルゴリズム持って怒鳴るアルゴリズムを解決し、時間の複雑さは

O（nlgnの*ログ（base3）n）を

for (a=1;a<=n;a++) 

    for (b=1;b<=n/2;b++) 

    for (c=1;c<=n;c*=3) 

     print("A") 

であることが判明しました：

for (a=1;a<=n;a++) 

     for (b=1;b<=a^2;b++) 

      for (c=1;c<=n/2;c++) 

      print("A2") 

を

時間の複雑さはO（n^4 lgn）になりますか？理由を説明してください。 あなたが

Answer 1

私はあなたが最初アルゴの時間計算量は（N * LGNが* n個のログ）Oであることを言ったと誤解されているかと思いますありがとうございました。それはO（n * log n）です。 bのループはO（n）ではなくO（lgn）で実行されます。

第2のアルゴリズムでは、cループを見ると、T _c = O（n）です。 cループを省略すると、実際にO（n）の時間が短縮されるので、cループは、nの乗数を時間複雑度の式に変換します。

aとbを見てみましょう。 bは、aの値に依存します。回数bループの本体が実行されるが、 = 1 + 4 + 9 + 16 + B

T _{です... + N}

これはよく、式を知っています自然数の2乗の和のうちの1つです。

∑ N = N（N + 1）（2N + 1）/ 6 = O（N ）

最終的に我々は

T C、B、 = T _、 B * T _C = O（N ）* O（N）= O（N ）

私は何らかの理由で、n/2とO（lgn）を関連付けています。ループfor(i=1;i<=n/2;i++)はfor(i=1;i<=n;i++)よりも2回少なく実行されますか？それらは両方とも複雑さO（n）を有する。それはlgnとは関係ありません。