大O符号中的指数

Question

3ⁿ = O(2ⁿ)吗？(3/2)ⁿ = O(2ⁿ)呢？你能解释一下答案吗？

对于第一个问题，我认为是错误的。因为无论您将2ⁿ乘以什么常数C，3ⁿ都会增长得更快。第二个问题也是同样的道理。

那么log(3ⁿ) = O(log (2ⁿ) )呢？我认为我们无法确定这个问题，因为我们不知道log的底数。

- Kalon

---

对数的底数通过一个常数因子改变数字，所以这并不重要。 - Joni

Answer 1

让我们证明一个更强的结论：对于任意常数r₀和r₁，其中1 ≤ r₀ ＜ r₁，有r₀ⁿ = O(r₁ⁿ)成立且r₁ⁿ = r₀ⁿ不成立。这证明了你的结果是一个特例，因为1 ＜ 3/2 ＜ 2。

为了证明第一部分，我们将展示r₀ⁿ = O(r₁ⁿ)。为此，我们将使用大O符号的定义，并找到n₀和c的值，使得对于任何n > n₀，我们都有以下不等式：

r₀ⁿ ≤ c r₁ⁿ 我们可以选择n = n₀，并且可以选择c = 1。上述不等式成立，因此根据定义，我们有r₀ⁿ = O(r₁ⁿ)。

为了证明第二部分，我们将展示r₁ⁿ ≠ O(r₀ⁿ)。为此，我们将采用反证法。为了推导矛盾，假设存在c和n₀的选择，使得对于任何n > n₀，我们都有以下不等式：

r₁ⁿ ≤ c r₀ⁿ 取两边的对数得到：

n log r₁ ≤ log (c r₀ⁿ) n log r₁ ≤ log c + n log r₀ n (log r₁ - log r₀) ≤ log c n log(r₁ / r₀) ≤ log c n ≤ log c / (log(r₁ / r₀))

但现在我们遇到麻烦了，因为这个语句应该适用于任何n的选择。然而，如果我们选择的n大于log c / (log(r₁ / r₀))，则该语句变为假。

我们遇到了矛盾，因此我们的假设必定是错误的。因此，如果1 < r₀ < r₁，那么r₁ⁿ ≠ O(r₀ⁿ)。

希望这可以帮助您！

- templatetypedef