如何证明这一点？

假设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

回答