指數大O等效

Question

我一直在試圖解決一個問題幾天了。我環顧網絡尋求幫助，我發現的唯一答案與我的結論相反。

這裏的問題：

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

得出的結論是「真」，而正確答案是：

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

的問題是，我不知道答案是如何確定的。一步一步的過程對我來說是最好的解釋。換句話說，3^n = 2^n是如何轉換成一個對數的，我們如何確定常數和n> = k的起點？

編輯： 也許這將更容易解釋哪裏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大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'? 

你的 「答案」 應該是7^n = 4^O(n)。您的顯示方式是7^n = 4^(n*log_4(7)) = 4^O(n)，作爲4^log_4(7) = 7。