哪个算法函数的增长速度更快，O(n^2) 或 O(n^2*log(n))，为什么？

Question

我将 n 的随机值 1、2、4、8、16、32 和 64 应用于函数 (n^2) 和 ((n^2)*log(n))。这些值n^2 的值高于 ((n^2)*log(n)) 的值，但在某些时候 ((n^2)*log(n)) 的值超过 (n^2) . table 的值是：

      n     n^2       (n^2 *log(n))
      1     1          0
      2     4          1.2
      4     16         9.6
      8     64         57.79
      16    256        308.25
      32    1156       1541.27
      64    4096       7398.11

从上面的 table 中，可以得出哪个算法函数的增长速度更快，为什么？

Answer 1

如果log是以10为底的对数，则log(10)=1，即n^2*log(n)>n^2对n>10。对于所有其他对数底数也是如此，即如果 log(n,b) 是 n 底数 b 的对数，则 n^2*log(n,b)>n^2 对应 n>b。

Answer 2

复杂性分析通常侧重于渐近行为，因为我们通常只关心进行大型计算时的性能（小问题规模的低效计算不是典型的研究对象）。

鉴于此，小输入的行为通常被忽略，我们说一个函数从上面渐近地绑定 (f = O(g))，这意味着 f 的增长不比 g 快，如果它最终总是案例.

显然，n^2 log(n) 最终总是大于 n^2，因为 log(n) 最终假定对于任何对数底数都大于 1 的值，之后 n^2 log(n) 是总是大于 n^2。的确，对于小于对数底的值，它具有较小的值，但只会有少量这样的输入大小。

Answer 3

对于某些小值 n^2 比 n^2*logn 快的原因是 log_b(n) < 1 对于所有 n < b。您似乎正在使用 log₁₀，所以该点在 8 和 16 之间。

  n  n^2  logn  n^2*logn
------------------------
  1    1  0.00     0.00
  2    4  0.30     1.20
  4   16  0.60     9.63
  8   64  0.90    57.80  ^^^ logn < 1
 16  256  1.20   308.25  vvv logn > 1
 32 1024  1.51  1541.27
 64 4096  1.81  7398.11

在那之后，logn 大于 1 并保持增长（尽管越来越慢），这意味着对于所有更高的值，n^2*logn 比 [=11 更大且增长更快=].对于 n 的一些小值来说它更小是无关紧要的，就像对于一些小输入来说，具有恒定复杂度的函数可能比指数函数慢。

Answer 4

我们想知道的是：log(n) 会大于 1 吗？

如果我们比较O(n²)和O(n² log(n))，我们需要知道log(n)是大于还是小于1。正如你所说，我正在考虑log(n)作为底数 2.

的对数

log(n) > 1   
n > 2^1
n > 2

在n > 2之后，log(n) > 1，也就是说O(n²) < O(n² log(n))对所有n > 2。

Answer 5

可以通过限制这两个来显示：

lim_{n \to \infty} n^2 / (n^2 * log(n)) = lim_{n \to \infty} 1 / log(n) = 0

最后一步是因为log函数是严格递增函数。因此，根据极限结果，这意味着 n^2 = o(n^2 * log(n))（小哦）并且 n^2*log(n) 的增长速度快于 n^2。

哪个算法函数的增长速度更快，O(n^2) 或 O(n^2*log(n))，为什么？

Which algorithmic function is faster in its growth ,O(n^2) or O(n^2*log(n)) and why?

algorithm

function

calculus