algorithm - 是否有复杂度为 O(log n) 的函数，而 power(2, f) 不在 O(n) 中

Question

无法弄清楚这一点:

是否有函数 f 使得:

f(n) is in O(log n)

但是，

2^(f(n)) is not in O(n)

应该是正确的，但我不明白为什么。

Answer 1

是的，请考虑以下示例:

A = logn + logn/2，所以 A = O(log n)

2^A = 2^{logn + logn/2} = 2^logn * 2^logn/2 = n *n/2 = 1/2n² != O(n)

(更具体地说，2^A = ω(n)，这意味着它比线性函数增长得更快。)