O(3^n) 还写成 O(2^n) 吗？
Is O(3^n) still written as O(2^n)?
我想知道具有指数最差时间复杂度的算法是否应该始终表示为 O(2^n)。例如，如果我有一个算法，每次增加输入大小的操作都是三倍，我会把它的时间复杂度写成 O(3^n)，还是仍然被归类为 O(2^n).
任何正式的解释将不胜感激。
不对，O(2^n) 和 O(3^n) 不同。如果 3^n 是 O(2^n)，那么对于所有大的 n，都会有一个常数 k，使得 3^n <= k * 2^n。没有这样的 k，因为 3^n / 2^n 是 (3/2)^n 可以任意变大。
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 不可能对所有 n ≥ n0 都成立，对任何常量 c。
我想知道具有指数最差时间复杂度的算法是否应该始终表示为 O(2^n)。例如，如果我有一个算法，每次增加输入大小的操作都是三倍，我会把它的时间复杂度写成 O(3^n)，还是仍然被归类为 O(2^n).
任何正式的解释将不胜感激。
不对，O(2^n) 和 O(3^n) 不同。如果 3^n 是 O(2^n)，那么对于所有大的 n，都会有一个常数 k，使得 3^n <= k * 2^n。没有这样的 k，因为 3^n / 2^n 是 (3/2)^n 可以任意变大。
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 不可能对所有 n ≥ n0 都成立，对任何常量 c。