大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视为常数吗？

- Jinny

---

有点跑题，但是... 如果你的投资每年给你10％的回报，你肯定会注意到 1.1^n 与一个常数的不同！在7.27年内，你的初始投资将翻倍！ - eddie

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!

我建议您查看大O符号的正式定义。但是，为了简单起见，列表顶部的函数比较底部的函数慢地趋近于无穷大。
例如，如果您在图表上放置两个函数，您会发现一个函数最终会超过另一个函数，并且会更快地接近无穷大。

请查看this，将n^2与2^n进行比较。您会注意到2^n正在超过n^2并更快地接近无穷大。
您还可以查看此页面中的图表。

- A. Sarid

---

我认为你系列中的最后三个需要解释一下（即为什么n^8621909，1.1^n和n!以这种顺序出现）。 - Tim Biegeleisen

"2的log(x)次幂在数学上等于n"。不是这样。"2^(以2为底的log x的值)等于n。然而，O(2^log(x)) = x。 - intboolstring

@intboolstring 感谢您的纠正，使它更加精确。我已相应地编辑了我的答案。 - A. Sarid

Answer 2

1. 2^log(x) = x，因此2^log(log(n)) = log(n)，增长速度比2ⁿ慢得多。

2. 1.1ⁿ肯定不是常数。 1.1ⁿ趋向于无穷大，而常数显然不是。

- Ami Tavory

---

请问您需要将这些函数按增长速度从慢到快排序吗？我可以帮忙进行翻译。 - Tim Biegeleisen