algorithm - 大O符号混淆

在回答这个问题时，我遇到了一些困难。问题是:按从最慢到最快的增长顺序对以下功能进行排序:

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

我对这个问题的回答是

n，3n

nlogn，6nlogn

4n ^ 2(等于n ^ 2)

7n ^ 3 – 10n(等于n ^ 3)

文字

n ^ 8621909

2 ^ loglogn

1.1 ^ n(指数2 ^ 0.1376n)

n!

我只是想知道:我可以假设2^(loglogn)与2^n具有相同的增长量吗？我应该将1.1^n当作常量吗？

最佳答案

否。假设日志位于基数2中，那么2^log(n)在数学上等于n，所以2^(log(log(n)) = log(n)相等。当然，它与2^n的增长不同。



不能。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中的图。

关于algorithm - 大O符号混淆，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/39064827/