big-o - 指数中大O的含义

Question

这个表达式是什么 f(n) = 2^O(n) 意思是，以一种完全正式的方式？

Answer 1

语句f(n) = 2^O(n)等价于

log_2(f(n)) = O(n)

(实际上，任何对数都可以)，所以这意味着存在一些常量 C > 0 使得

log_2(f(n)) <= C*n  <=> f(n) <= 2^(C*n)

对于所有足够大的n。现在，a^b*c = (a^b)^c，所以另一种表达方式是

f(n) = O(b^n)

对于某些 b > 0。这个 b 可能是 1.5，或者 4，或者 1000000000000，所以它不会告诉你太多。它给你的只是 f 是指数级的，所以它比 O(n!) 渐近更好，但它并没有告诉你它是否非常糟糕，糟糕，真的糟糕或真正灾难性的糟糕。