是否有复杂度为 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

好吧，是也不是...

您的定义有多精确？ log(n) 对你来说是什么？

在工程中 log(n) 通常表示 log_10(n)，在 CS 中通常是 log_2(n) 但是 O(log_m(n)) 确实与 class 相同=15=].

那你说的2**(fn(n))是什么意思？ fn(n) return 是整数吗？

问题没有很好地提出。

Answer 2

是的，请考虑以下示例：

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)，这意味着它比线性函数增长得更快。）