我想知道一个最坏时间复杂度为指数级的算法是否应该总是表示为 O(2^n)。例如,如果我有一个算法,其操作每次增加一次输入大小就会增加三倍,那么它的时间复杂度应该写成 O(3^n),还是仍然归类为 O(2^n)。任何正式的解释都将不胜感激。
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都成立。
不,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。
3^n
相当于2^(log3 * n)
。因此,3^n
的复杂度与m=log3*n
的2^m
相同。 - CoronAC
,使得对于所有足够大的n
,都有3^n <= C*2^n
?绘制3^n / 2^n
的图表应该很清楚地提示答案,而数学证明也不难。 - Nate Eldredge