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, or 1000000000000, 所以它不会告诉你太多。它给你的f只是指数，所以它渐近优于O(n!)，但它并没有告诉你它是非常糟糕、糟糕、非常糟糕还是真的非常糟糕。