次のプログラムの時間の複雑さは何ですか？

Question

次のプログラムの時間の複雑さは何ですか？どのように複雑さを計算する？複雑さの上限と下限は何ですか？ O（N^2）である（N^2-N）回の反復であるあなたは、N末端からつもり

あなたの外側のループでは

for(i=n;i<=n^2;i++) 
    for(j=1;j<=i*log(i);j++) 
     a[i][j]+=3*i*j; 

Answer 1

、> N^2、。 O（（N^2）ログ（N））

a[i][j]+=3*i*j;がOである

あなたは1-つもりあなたの内側のループでは

、>約（N^2）ログ（N^2） （1）、あなたは貢献しません。

が一緒にそれを置く、あなたはO（N^2 * N^2 * log（n）の）はO（n^4ログ（N））で、

Answer 2

マイクの答えはちょうどステップを拡大し、正確である必要があり別の方法で

内部ループ：CONST * I *ログ（I） 外部ループ：私は、（i）

O（アルゴ）ログ* CONSTの：合計（N^2 I 1を超える）を= 0（i * log（i）のSum（i以上1：n^2））

http://en.wikipedia.org/wiki/Summation

和（I 1以上：メートル）の（iのログ（i）を*）私たちは（

Oを取得シータ（M^2 *ログ（M））

代替のM = N^2 = （実際にはアルゴのシータ）

編集：私はちょうど外側に気づいた（アルゴ）= O（n^2）^ 2 log（n^2）ループは私がn：n^2以上ですが、答えは同じです