Complexidade de $ o (\ log (n ^ n)) $ vs $ o (\ log (n!)) $

Question

é $ o (\ log (n ^ n)) ?Existe algum algoritmo bem / prático com esse tipo de complexidade?

e também, para verificar minha compreensão da complexidade algorítmica, são essas duas $> O (n \ log (n)) $ ?

Eu estou apenas começando com este tópico e não tenho certeza se estou acertando.

Obrigado e fique seguro.

Answer 1

$ o (\ log n ^ n) $ e $ o (\ log n!) $ ambos descrevem o mesmo conjunto de funções.

Observe que $ (\ frac {n} {e}) ^ n \ le n!\ le n ^ n $ e, portanto,:

$ o (n \ log n)= o (n \ log \ frac {n} {e})= o (\ log (\ frac {e}) ^ n) \ subseteq o (\ log n!) \ subseteq o (\ log n ^ n)= o (n \ log n) $ .

Isso mostra que todos os conjuntos acima coincidem.

Answer 2

$ n ^ n $ é muito maior que n!. O primeiro multiplica n x x n x n x ... x n (n vezes), o último multiplica 1 x 2 x 3 x 4 x ... x n. Por isso é que $ o (\ log (n ^ n)) não é verdadeiro. $ o (\ log (n ^ n))> O (\ log (n!)) $ é menos óbvio, mas também não é verdade.

Isso é porque estamos levando o logaritmo em ambos os lados. Tirar logarithms mudanças produtos para somas e expoentes para produtos (muito aproximadamente). E se tomarmos o produto para N!, É óbvio que temos fatores N / 2 maiores que n / 2, então n! > $ (n / 2) ^ {n / 2} $ . Tomando o logaritmo, log n! > (N / 2) LOG (N / 2). Para n> 4 temos N / 2> $ n ^ {1/2} $ , portanto, log n / 2> (log n) / 2, portanto log n ! > (N / 2) LOG (N / 2)> N / 4 log n= 1/4 log $ n ^ n $ .

Então log n!= $ \ theta (\ log n ^ n) $ .