如何證明這一點？

假設f（n）∈O（log2（n））。我們可以說2^f（n）∈O（n）？我可能會混淆自己，但數學上不會這是真的嗎？由於2^log2（n）將是n，並且n就複雜性而言將是O（n）的元素？但是，我將如何證明這一點？如何證明這一點？

2016-09-19 treasure21

我覺得這個問題應該發佈在cs.stackexchange.com – ianalis

兩者都不是真的。 2^n在n中不是線性的; log（n）不是n。你需要了解Big-Oh符號。 – duffymo

@duffymo如果有人向Big-Oh表示法請求幫助，那麼評論他們需要了解Big-Oh表示法有點多餘。（如果你問我，還有一點點居高臨下的感覺）。 –

不，這是不正確的。你可以轉化爲

2^f(n) = n^O(1)

爲f(n) < c*log2(n)（大型n）只意味着

2^f(n) < 2^(c*log2(n)) = (2^log2(n))^c = n^c

與一些未公開的不斷c。

2016-09-19 17:31:58 LutzL

回答