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

只是想知道我可以假设2 ^(loglogn)与2 ^ n具有相同的增长吗？

不.假设日志在基数2中,那么在2^log(n)数学上等于n,所以2^(log(log(n)) = log(n).当然,它没有同样的增长2^n.

我应该把1.1 ^ n作为常数？

号码1.1^n仍然是一个n不容忽视的指数- 当然它不是一个常数.

正确的顺序是:

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

我建议看一下Big-O表示法的正式定义.但是,为简单起见,列表的顶部比较低的函数慢到无穷大.
例如,如果您将其中两个函数放在图形上,您将看到一个函数最终会通过另一个函数并且将更快地变为无穷大.

看看这个比较n^2有2^n.你会发现它2^n正在传递n^2并且更快地进入无限远.
您可能还想查看此页面中的图表.