大 O 符号中的指数

Question

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

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

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

Answer 1

让我们实际证明一个更强的结果：对于任何常数 r ₀和 r ₁，其中 1 ≤ r ₀ < r ₁，r ₀ ⁿ = O(r ₁ ⁿ ) 为真，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 ₀ ⁿ

取双方的对数得到

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 ₀ ⁿ )。

希望这可以帮助！