algorithm - O(n^2) 是否大于 O((n^2)logn)

Question

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 的复杂度是多少？

score 15 · Accepted Answer

O(n^2)是的一个子集，O((n^2) * log(n))因此第一个是“更好的”，很容易看出，因为log(n)它是一个递增函数，通过与它相乘，你会得到一个比原始函数“更高”的函数（f(n) <= f(n) * log(n)对于每个递增的非负f和n>2）

您给出的代码快照是O(nlog(n))，因为内部循环在log(n)每次外部循环迭代时重复多次，而外部循环重复 n/2 次 - 这给了n/2 * log(n)你O(nlog(n))

score 2 · Accepted Answer

Ln(e) == 1，所以任何大于 e (~2.7) 的东西都会给出 Ln(n) > 1。

因此，对于所有 n > e，O(n^2 ln(n)) 将 > O(N^2)

score 0 · Accepted Answer

我假设你的意思是O((n^2) * log n)，但答案是一样的，如果是，你需要证明的基本上是一样的n^(2 * log n)。我也只会考虑非负函数，以节省一些绝对值的麻烦。

答案是O(n^2)的严格子集O((n^2) * log n)。它更小。

首先证明它是一个子集：假设f是O(n^2)。那么存在M和k这样的，对于所有n >= M, f(n) <= k(n^2)。

让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 n，所以g为 in O((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 >= M来说，g(n) <= k * n^2。

3 回答 3