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!)ていますが、それがかなり悪いか、悪いか、本当に悪いか、本当に壊滅的に悪いかはわかりません。