Значения большого O в показателе

Question

Что означает это выражение е (п) = 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 большой. Теперь, ^{Ь * с} = (а ^б) ^с, так что еще один способ положить это сказать

f(n) = O(b^n) 

для некоторых b > 0. Это b может быть 1.5, или 4, или 1000000000000, так что это не говорит вам слишком много. Все это дает вам то, что f экспоненциально, поэтому он асимптотически лучше, чем O(n!), но он не говорит вам, довольно ли плохо, плохо, очень плохо или действительно катастрофически плохо.