指数函数的大O表示法

Question

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

Answer 1

因为没有任何恒定值k可以满足3^n <= k * 2^n任意大的不等式n.因此f(n) = 3^n不是其中的一员O(2^n).

这是最流行的集合理论 ZFC 中的一个公理：https://en.wikipedia.org/wiki/Zermelo%E2%80%93Fraenkel_set_theory。它只是说“两个集合相等，如果它们包含相同的元素”。没有人在真正的证明中引用它，但我只是试图说服 SO 开始使用实际的数学推理而不是直觉（通过使用数学术语极其冗长）。如果您只是想在编写代码时决定使用哪种实现，则可以使用直觉。当有人说“证明这一点”时，我认为你应该，你知道，使用数学:) (3认同)
@roliu：嗯，我认为这里的大多数人都会对“如果没有相同的成员，则两组不相等”感到满意，而不必求助于证明/术语！集合论公理可能有点超出了 SO 的范围（相对于 CS/Math StackExchange）。但感谢您的链接，我总是有兴趣学习一些有趣的数学...... (2认同)