4

O(n^2) は O(n^2 log n) より大きいですか?
もし、そうなら ？どうやって ？
これについて簡単な例を挙げることができますか。
また、
以下のコードの複雑さは何ですか。 

int unknown(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;
     }
  }
return k;
}

戻り値 k の複雑さとは?

4

3 に答える 3

15

O(n^2)は のサブセットであり、したがって最初のほうが「より良い」です。は増加する関数であるため、何かを乗算することにより、元の関数よりも「高い」関数が得られるO((n^2) * log(n))ことが簡単にわかります (増加する非負およびごとに)log(n)f(n) <= f(n) * log(n)fn>2

O(nlog(n))内側のループはlog(n)外側のループの反復ごとに回数を繰り返し、外側のループは n/2 回繰り返すため、指定したコード スナップは ですn/2 * log(n)。O(nlog(n))

于 2013-02-12T09:31:56.117 に答える
2

Ln（e）== 1であるため、e（〜2.7）より大きい値は、Ln（n）>1になります。

したがって、n> eであるすべてのnについて、O（n ^ 2 ln（n））は> O（N ^ 2）になります。

于 2013-02-12T09:31:38.097 に答える
0

私はあなたが意味すると仮定していますO((n^2) * log n)が、答えは同じであり、証明する必要があるのは基本的に同じですn^(2 * log n)。また、絶対値をいじる手間を省くために、非負関数のみを検討します。

答えはO(n^2)、 の厳密なサブセットですO((n^2) * log n)。小さいです。

最初にそれがサブセットであることを証明しfますO(n^2)。次に、すべての 、 などがありMます。kn >= Mf(n) <= k(n^2)

Let L = max(M, e)(e は対数の底)。次に、すべてn >= Lのlog(n) >= log(e) == 1(since n >= 1) およびf(n) <= k(n^2)(since n >= M) について。

したがって、すべてのn >= L、f(n) <= k(n^2) * log(n)。もそうfですO((n^2) * log n)。

次に、それが厳密なサブセットであることを証明しgます。g(n) = (n^2) * log ngO((n^2) * log n)

についてはk、 を取りL = e^kます。次に、任意のn > L場合log(n) > kなどg(n) > n^2 * k。

したがって、gはO(n^2)存在Mし得ないので、ではありませkん。n >= Mg(n) <= k * n^2

于 2013-02-12T09:49:42.297 に答える