時間の複雑さ（入れ子にされたループ）

これの時間の複雑さをどうやって解決しますか？時間の複雑さ（入れ子にされたループ）

int count=0; 

for (int i=1 ; i < n; i*=4) 

    for (int j=1;j<=n;j++) 

       count++;

2016-08-22 WWBM

であるn*(log_4(n)+1)回内部ループ反復を与えます。また、あなたは助けを求めましたが、正確にどこにいられたのかを実際には説明しませんでした。あなたは基本的に私たちに宿題を与えました。 –

ちょうどコードスニペットからT（n）を得る方法を見つけようとしています。 t（n）= O（n^2）かO（log（n））になりますか？その宿題ではない。過去のテストからのその質問。本当に問題を理解しているのです – WWBM

それはどちらかというとそれがなぜだと思いますか？繰り返しますが、あなたはそれを理解する方法を説明し、あなたが混乱している部分について非常に具体的でなければなりません。 –

TL; DRは：投稿コードの複雑さは、次のとおりです。

O(nlogn)はのは、内側からそれを分析してみましょう。内部ループは、iの各値に対して正確にn回繰り返されます。

外側ループはそれ自体を繰り返すが、i < nとiは毎回4を掛けている。これは、最初の反復の後に、i=1、次にi=4, i=16, i=64, ....、およびk'thの反復の後にi = 4^(k-1)を意味します。

i >= n 
4^(k-1) >= n 
log_4(4^(k-1)) >= log_4(n) 
k-1 >= log_4(n).

これは外側のループはlog_4(n) + 1を繰り返すことになります意味：
これは、ときに停止する、を意味します。一緒にそれをすべてを合計

はあなたに、少なくともコードの行のあなたのカップルをフォーマットするために時間がかかるO(nlogn)

2016-08-22 20:09:38 amit

ありがとうございます！正直そんなに意味をなさない！ – WWBM

答えて