algorithm - 指数函数的大 O 表示法

Question

我注意到 1000n 或 10n 的 big-O 与 O(n) 相同，但 2^n 和 3^n 的 big-O 不同：O(2^n) 和 O(3^n)，我不明白为什么我们不能忽略这种情况下的常量（2 或 3）以及是否有任何数学证据证明这一点？

Answer 1

因为不存在满足任意大k不等式的常数值。因此不是 的成员。3^n <= k * 2^nnf(n) = 3^nO(2^n)

请参阅http://en.wikipedia.org/wiki/Big_O_notation#Family_of_Bachmann.E2.80.93Landau_notations。

Answer 2

尽管对于最初的提问者来说，这可能不再有用，但
我认为可以以更简单的方式处理它。

O-notation 的基本定义：如果 f(g) 在 O(g(n)) 中，
则存在一个有理数 c，它认为 f(g) = c * g(n)，对于 n >= n0
（n0 是您自己选择的数字）

让我们尝试将其应用于 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

这可能看起来像一个冲突，直到您意识到所有 n > 0 的 0.75^n < 1，这意味着如果您取任何 c > 1，它将大于 n = 0 的 0.67^n

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))

然后要 demostrade 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，那么极限的结果取决于常数，I如果 0 < a < 1 和 lim_{n->inf} a^n = inf 如果 a > 1，则表示 lim_{n->inf} a^n = 0；

为了更好地理解检查：Thomas H. Cormen、Charles E. Leiserson、Ronald L. Rivest 和 Clifford Stein 的算法介绍，第三版

我是算法教授，希望对你有所帮助。小心。