algorithm - O(3^n) 仍然写成 O(2^n) 吗？

Question

我想知 Prop 有指数最差时间复杂度的算法是否应该始终将其表示为 O(2^n)。例如，如果我有一个算法，对于输入大小的每个加法运算操作三倍，我会将其时间复杂度写为 O(3^n)，还是仍将其分类为 O(2^n)。

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

Answer 1

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

让我们假设这是真的。那么存在常量 c 和 n0 使得 3^n ≤ c * 2^n 对于所有 n ≥ n0.

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

但是，(3/2)^n → ∞ 为 n → ∞，所以 (3/2)^n ≤ c对于任何常量 c 的所有 n ≥ n0 不可能为真。