Big-O 符号混淆

Big-O notation confusion

我在做这道题的过程中遇到了一些困难。问题是：按照增长从慢到快的顺序对以下函数进行排序：

7n^3 − 10n, 4n^2, n, n^8621909, 3n, 2^(log log n), n log n, 6n log n, n!, 1.1^n

我对这个问题的回答是

  1. n,3n
  2. nlogn, 6nlogn
  3. 4n^2（等于n^2）
  4. 7n^3 – 10n（等于n^3）
  5. n^8621909
  6. 2^loglogn
  7. 1.1^n(指数 2^0.1376n)
  8. n!

只是想知道：我可以假设 2^(loglogn) 与 2^n 具有相同的增长吗？我应该把 1.1^n 作为常数吗？

  1. 2log(x) = x,所以2 log(log(n)) = log(n)，增长 far 比 2 慢n.

  2. 1.1n绝对不是常数。 1.1n趋于无穷大，常数显然不会。

Just wondering can i assume that 2^(loglogn) has the same growth as 2^n?

没有。假设日志以 2 为底，那么 2^log(n) 在数学上等于 n，因此 2^(log(log(n)) = log(n)。当然，它的增长速度不如 2^n.

Should I take 1.1^n as a constant?

没有。 1.1^n 仍然是 n 的指数，不能忽略 - 当然它不是常数。

正确的顺序是：

2^loglogn = log(n)
n,3n
nlogn, 6nlogn
4n^2
7n^3 – 10n
n^8621909
1.1^n
n!

我建议看一下Formal definition of the Big-O notation。但是，为了简单起见，列表的顶部比下面的函数更慢地到达无穷大。
例如，如果您将其中两个函数放在图表上，您会看到一个函数最终会超过另一个函数，并且会更快地达到无穷大。

看看 this 比较 n^2 和 2^n。您会注意到 2^n 正在超过 n^2 并更快地到达无穷大。
您可能还想查看 this page.

中的图表