math - 大 O 表示法中的指数

Question

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

我第一次弄错了，因为无论你将 2 ^{n乘以什么常数 C，3 n}的增长速度都比 2 ⁿ快。第二个也一样？

log(3 ⁿ ) = O(log (2 ⁿ ) ) 怎么样？我认为我们无法确定这一点，因为我们不知道日志的基础。

Answer 1

让我们实际证明一个更强的结果：对于任何常数 r ₀和 r ₁，其中 1 ≤ r ₀ < r ₁，r ₀ ⁿ = O(r ₁ ^{n ) 是真的，r} ₁ ⁿ = r ₀ ⁿ是假的. 这证明了您的结果是一种特殊情况，因为 1 < 3/2 < 2。

为了证明第一部分，我们将证明 r ₀ ⁿ = O(r ₁ ⁿ )。为此，我们将使用 big-O 的定义并找到 n ₀和 c 的值，这样对于任何 n > n ₀，我们都有

r ₀ ⁿ ≤ cr ₁ ⁿ

我们可以选择 n = n ₀并且可以选择 c = 1。然后上面的不等式成立，所以根据定义我们有 r ₀ ⁿ = O(r ₁ ⁿ )。

为了证明第二部分，我们将证明 r ₁ ⁿ ≠ O(r ₀ ⁿ )。为此，我们将通过矛盾进行。为了矛盾起见，假设存在 c 和 n ₀的选择，使得对于任何 n > n ₀，我们有

r ₁ ⁿ ≤ cr ₀ ⁿ

取双方的log得到

n log r ₁ ≤ log (cr ₀ ⁿ )

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的任何选择。但是，如果我们选择任何大于 log c / (log(r ₁ / r ₀ )) 的 n，则该陈述变为错误。

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

希望这可以帮助！