big-o - 是 O(log(n*log n) 可以认为是 O(log n)

Question

考虑我得到 f(n)=log(n*log n)。我应该说它的 O(log(n*log n)？还是我应该做 log(n*log n)=log n + log(log n) 然后说函数 f(n) 是 O(log n )?

Answer 1

首先，正如您所观察到的：

 log(n*log n) = log(n)  + log(log(n))

但是将 log(log N) 视为 N->large （正如 Floris 所建议的那样）。

例如，让 N = 1000，然后 log N = 3（即一个小数字）并且 log(3) 甚至更小，当 N 变得很大时，这仍然成立，即远远超过您的代码可能生成的指令数量。

因此，O(log(n * log n)) = O(log n + k) = O(log(n)) + k = O(log n)

另一种看待这个问题的方法是：n * log n << n^2，所以在最坏的情况下：

  O(log(n^2)) > O(log(n * log n))

所以，2*O(log(n)) 是一个上限，并且 O(log(n * log n)) = O(log n)

Answer 2

使用定义。如果 f(n) = O(log(n*log(n)))，则必须存在一个正常数 M 和实数 n ₀使得：

|f(n)| ≤ M |log(n*log(n))|

对于所有 n > n ₀。

现在让我们假设（不失一般性）n ₀ > 0。然后

对数（n）≥对数（对数（n））

对于所有 n > n ₀。

由此，我们有：

日志(n(log(n)) = log(n) + log(log(n)) ≤ 2 * log(n)

代入，我们发现

|f(n)| ≤ 2*M|log(n))| 对于所有 n > n ₀

由于 2*M 也是一个正常数，因此立即得出 f(n) = O(log(n))。

Answer 3

当然，在这种情况下，简单的变换显示两个函数渐近地相差一个常数因子，如图所示。

但是，我觉得值得提醒一个经典测试来分析两个函数如何渐近地相互关联。所以这里有一个更正式的证明。

您可以通过分析when来检查 dos 的f(x)相关性。g(x)lim f(x)/g(x)x->infinity

有3种情况：

1. lim = 无穷 <=> O(f(x))>O(g(x))
2. inf > lim > 0 <=> O(f(x))=O(g(x))
3. lim = 0 <=> O(f(x))<O(g(x))

所以

lim ( log( n * log(n) ) / log n ) =
lim ( log n + log log (n) )  / log n =
lim 1 + log log (n) / log n =
1 + 0 = 1

注意：我认为log log n / log n这是微不足道的，但您可以通过de l'Hospital Rule做到这一点。