コードΘ（nLogn）の時間的複雑性はどのようにしてですか？

-4

int n; 
int i, j, k = 0; 
    for (i = n/2; i <= n; i++) { 
     for (j = 2; j <= n; j = j * 2) { 
      k = k + n/2; 
     } 
    }

は、単にコードスニペットの時間の複雑さを計算する必要があるとの回答はΘ（nLogn）ですが、それはそれは本当に難しいことではありませんΘ（nLogn）コードΘ（nLogn）の時間的複雑性はどのようにしてですか？

ですから、情報のすべてを持っている：

ループは、我々がこれで終わる、乗算ので、ネストされています。なぜ計算できないのですか？ –

あなたのヒントはO（n！）ではありませんが、真剣に検討しても分からない場合は、そこにprintf呼び出しを入れて呼び出し頻度を追跡し、パターンを変更したときにパターンを見つけることができないかどうかを確認してください。ループサイズ？ –

"...Θ（nLogn）の仕方を説明できますか？" - どのようにして* *Θ（nLogn）になるかも説明できますか？ – WhozCraig

がどのように説明することができます。

外側ループはn/2回実行されます。つまり、複雑さはO(n)です。

内部ループは再びnに依存します。最初のループからのiには依存しません。内側ループの複雑さのために、外側ループを完全に無視することができます。どのように幸運！ jは毎回倍数で2となりますので、logarithm base 2です。つまり、O(log(n))です。

O(n log(n))

2016-04-25 17:22:01 bolov

答えて