与えられた時間の複雑さでアルゴリズムを作成してください

Question

そのような問題にどのようにアプローチするのですか？私はO（n）,O（n^2）などと基本的な時間の複雑さを知っていますが、O（m^2 *（log（n））^ 2）のアルゴリズムを作成する方法は、 O（log（n^2/m））？

は右例えばそれです： O（M^2 *（ログ（N））^ 2）

for(i=0; i<m; i++) 
    for(j=0; j<m; j++) 
    for(k=0; k<n; k*=2) 
     for(l=0; l<n; l*=2) 
      something() 

何秒約1？

編集：もう一つは（（N^2/m）のログ）= O（ログ（N）+ログ（N/M））

単にその

Oのようなものであるため

for(i=n;i>0;i/=2); 
for(j=n/m;j>0;j/=2); 

Answer 1

第四のネストされたループは、 第三のネストされたループは、O（Nログ）、 第二のネストされたループはO（M）、 O（ログn）である第一のループはO（mは）

このループはすべてネストされているので、全体の複雑さを増やすために乗算する必要があることは容易に理解できます。 O（m m log n * log n）= O（m^2 * n）^ 2）。

第3ループと第4ループがO（log n）である理由は、次のループではlが2となることです。したがって、mがループが繰り返される全体の数であれば、 l^m> = n - > mはO（log n）です。

同じ理由で、3番目のネストループもO（log n）です。あなたが持っている場合、同じ理由また

：

for(i=1;i<n*n/m ;i*=2) 

上記ループはO（ログ（N N/M））は、ループ反復の総数はMあれば理由： 私^ m> = n n/m→O（log（n * n/m））。

UPDATE

O（*（NログN/M））= O（ログN^2/M）= O（2log（N/M））= O（ログ（N/M ））であり、O（log（n）+ log（n/m））ではない。

はまた、あなたが持っている場合：

for(i=n;i>0;i/=2) 
    for(j=n/m;j>0;j/=2) 
     something(); 

をこれには全体的にはO O（）N（ログ）アウターループとOのための（N/Mログ）内部ループのためにである（ログ（N ）* log（n/m））ではなく、O（log（n）+ log（n/m））ではない。