指数大 O 等效

Question

几天来我一直在尝试解决一个问题。我在网上四处寻找帮助，但我找到的唯一答案与我的结论相反。

这是问题：

   **3^n = 2^(O(n))   True or False?**

结论是"TRUE"，正确答案是：

3^n = 2^(O(n)) since 3^n = 2^(n*log_2(3)) = 2^(O(n))

问题是我不知道答案是如何确定的。一步一步的过程对我来说是最好的解释。换句话说，3^n = 2^n 是如何转换为对数的，我们如何确定常数和 n >= k 的起点？

编辑：在这个受过良好教育的 guess.The 解决方案中，解释 2 和 3 的来源可能会更容易，其中有一个 3 和两个 2。

If f(n) = 3^n and g(n) = 2^n 

The 3 in 2^(n*log_2(3)) must be coming from f(n)?
The 2 in 2^(n*log_2(3)) must be coming from g(n)'s base?
----> Is the log_2 a constant??

换句话说，如果问题是

7^n  = 4^(O(n)) ?

正确答案是

4^(n*log_2(7))

How is k determined, where all n >= k?

提前致谢！！！

Answer 1

教授说得对。他们的逻辑如下： 3^n = (2^log_2(3))^n = 2^(n*log_2(3)) = 2^O(n)

log_2(3) = z 表示“2 的 z 次方给出 3”，我们将 2 提高到这个指数，所以我们得到 3^n.

基本上他们表明，通过将 2^x 中的指数乘以一个常数，您可以将底数更改为 3。Big O 丢弃常量，因此底数是 2 还是 3 并不重要。

编辑：

If f(n) = 3^n and g(n) = 2^n 

The 3 in 2^(n*log_2(3)) must be coming from f(n)?
The 2 in 2^(n*log_2(3)) must be coming from g(n)'s base?
----> Is the log_2 a constant??

我不确定你想问什么。 log_2的常数是常数。

4^(n*log_2(7))

Where k = 7, and n >= 7 and 2 is the constant 'c'?

您的 "answer" 应该是 7^n = 4^O(n)。您的显示方式是 7^n = 4^(n*log_4(7)) = 4^O(n)，如 4^log_4(7) = 7。

指数大 O 等效

Exponential Big-O Equivalency

big-o

computer-science