指数中大O的含义

Question

这是什么表达˚F（Ñ）= 2 ^Ö（Ñ）平均，以精确的正式的方式？

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!)，但是它并没有告诉您它是非常糟糕，糟糕，真正糟糕还是真正灾难性的糟糕。