指数函数的大O表示法

Question

我注意到1000n或10n的大O与O(n)相同，但2^n和3^n的大O是不同的：O(2^n)和O(3^n)，我不理解的是为什么在这种情况下我们不能忽略常数(2或3)，是否有任何数学证明可以证明这一点？

- fYre

---

在大O符号中，你不会忽略常数，而是忽略系数。数字2和3是基数，而不是系数。 - kqr

你能陈述一下大O符号的定义吗？记住，大O符号有一个数学定义，不能完全凭直觉使用。我认为仅仅记住“有时可以忽略常数”是一个不好的习惯。 - rliu

Answer 1

由于不存在常数k的值能够满足不等式3^n <= k * 2^n对于任意大的n都成立。因此，f(n) = 3^n不属于O(2^n)。

详见http://en.wikipedia.org/wiki/Big_O_notation#Family_of_Bachmann.E2.80.93Landau_notations。

- Oliver Charlesworth

---

准确来说，你正在展示一个反例，证明了 O(3^n) = O(2^n) 这个命题不成立。特别地，使用你上面提到的论证，f(n) = 3^n 在 O(3^n) 中但不在 O(2^n) 中。因此，根据外延公理，这两个集合不相等。 - rliu

@roliu：我不知道那个公理是什么，但是是的，那是暗示的参数 ;) - Oliver Charlesworth

在最流行的集合论ZFC中，这是一个公理：https://en.wikipedia.org/wiki/Zermelo%E2%80%93Fraenkel_set_theory。它的意思是“当且仅当两个集合的元素相同时它们相等”。在实际的证明中，没有人会引用它，但我正在尝试说服SO开始使用真正的数学推理而不是直觉（通过使用极端冗长的数学术语）。如果您只是在编写代码时想决定使用哪个实现，则可以使用直觉。当有人说“证明这个”时，我认为您应该使用数学 :) - rliu

@roliu：嗯，我认为大多数人都会满意于“如果两个集合的成员不相同，则它们不相等”，而无需诉诸于证明/术语！ 集合论公理可能有点超出了SO的范围（与CS / Math StackExchange相比）。 但是感谢您提供的链接，我总是很有兴趣学习一些有趣的数学知识... - Oliver Charlesworth

是的。大多数S.O.上的人都无法证明他们的能力。 (包括我在内。) 这个问题非常深奥和超出了范围。>: - ELLIOTTCABLE

七个月后，我通过不同的途径再次遇到了这个问题，并专门寻找@rliu提供的信息。这只是说明了一个事实。 - ELLIOTTCABLE

Answer 2

尽管对于原提问者来说这可能已经没有用处了，但我认为可以更简单地解决。

O-符号的基本定义：如果f(g)在O(g(n))中，则存在一个有理数c使得对于n ≥ n0（n0是您自己选择的数字），f(g) = c * g(n)。

让我们尝试在O(2^n)中应用3^n：

3^n = 2^n * c 3^n = 2^n * (3^n / 2^n) 3^n = 2^n * (3/2)^n 3^n = 2^n * 1.5^n

这意味着c = 1.5^n，它不是一个有理数，而是一个指数函数。

另一方面，在O(2^n)中应用3^n，我们将得到2^n <= 3^n * (2/3)^n。

这似乎是一个矛盾，直到您意识到0.75^n < 1对于所有n> 0，这意味着如果您取任何c> 1，则它将大于从n = 0开始的0.67^n。

- Work of Artiz

Answer 3

比较两个复杂度f(n)和g(n)，您可以应用极限：lim_{n->\inf} f(n)/g(n)，然后有三个可能的答案：

1) lim_{n->\inf} f(n)/g(n) = 0; 这意味着f(n) ∈ O(g(n))，且g(n) ∉ O(f(n))

2) lim_{n->\inf} f(n)/g(n) = +/- inf; 这意味着f(n) ∉ O(g(n))，且g(n) ∈ O(f(n))

3) lim_{n->\inf} f(n)/g(n) ∈ 实数; 这意味着f(n) ∈ O(g(n))，且g(n) ∈ O(f(n))

因此，要证明2^n ∈ O(3^n)，您可以按如下操作

lim_{n->\inf} 2^n/3^n = lim_{n->\inf} (2/3)^n = 0

展示了，我们还证明了3^n ∉ O(2^n)，很容易看出 2/3 < 1，这使得极限收敛于0，因此极限的结果取决于常数。我的意思是，如果0 < a < 1，则 lim_{n->inf} a^n = 0，如果a > 1，则 lim_{n->inf} a^n = inf；

为了更好地理解，请查看：《算法导论》第三版，作者：Thomas H. Cormen，Charles E. Leiserson，Ronald L. Rivest 和 Clifford Stein。

我是算法教授，希望对您有所帮助。注意保重。

- Carlos Villaseñor