これを証明する方法は？

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表記を理解する必要があるとコメントするのは少し冗長です。（あなたが私に尋ねるなら、ちょっと納得しています。） –

いいえ、該当しません。あなただけのいくつかの未公開定数cと

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

を意味します（大n用）f(n) < c*log2(n)として

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

に変換することができます。

2016-09-19 17:31:58 LutzL

答えて