algorithm - Big-O 符号混淆

Question

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

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 作为常量吗？

Answer 1

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 中的图表.