O(3^n) 还是写成 O(2^n) 吗？

Question

我想知道具有指数最坏时间复杂度的算法是否应该始终将其声明为 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.

最后一个要求相当于(3/2)^n ? cfor all n ? n0。

然而，(3/2)^n ? ?因为n ? ?，所以(3/2)^n ? c不可能是所有真正的n ? n0任何常数c。