O(3^n) 仍然写作 O(2^n) 吗？

Question

我想知道一个最坏时间复杂度为指数级的算法是否应该总是表示为 O(2^n)。例如，如果我有一个算法，其操作每次增加一次输入大小就会增加三倍，那么它的时间复杂度应该写成 O(3^n)，还是仍然归类为 O(2^n)。

任何正式的解释都将不胜感激。

- BinaryGamer

---

3^n 相当于 2^(log3 * n)。因此，3^n 的复杂度与 m=log3*n 的 2^m 相同。 - CoronA

回到定义：是否存在一个常数C，使得对于所有足够大的n，都有3^n <= C*2^n？绘制3^n / 2^n的图表应该很清楚地提示答案，而数学证明也不难。 - Nate Eldredge

Answer 1

3^n != O(2^n).

假设它是真的。那么存在常数和n0，使得对于所有n ≥ n0，都有3^n ≤ c * 2^n。

最后一个要求等价于对于所有n ≥ n0，都有(3/2)^n ≤ c。

然而，随着n → ∞，(3/2)^n → ∞，因此对于任何常数，(3/2)^n ≤ c不能对所有n ≥ n0都成立。

- Jasmeet

Answer 2

不，O(2^n)和O(3^n)是不同的。如果3^n是O(2^n)，那么就会有一个常数k，使得对于所有大的n，3^n <= k * 2^n。但是因为3^n / 2^n是(3/2)^n，它会无限增长，所以不存在这样的k。

- Paul Hankin