意味

Question

何の正確な正式な方法で、この表現F（N）= 2 ^O（N）を意味するのでしょうか？

Answer 1

声明f(n) = 2^O(n)は

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

（実際には、任意の対数が行います）と等価であるので、十分なn大きなすべてのためのいくつかの定数C > 0よう

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

があることを意味します。さて、^{のb * C} =（^B）C^{ので、それを置くための別の方法は、いくつかのb > 0ため}

f(n) = O(b^n) 

を言うことです。このbは1.5、4、または1000000000000となる可能性があります。それがあなたに与えるのは、fが指数関数的なので、O(n!)よりも漸近的に優れていますが、かなり悪い、悪い、本当に悪い、または本当に大惨事的に悪いかどうかはわかりません。