Complexité de $ O (\ journal (n ^ n)) $ vs $ o (\ journal (n!)) $

Question

est $ O (\ journal (n ^ n)) ?Y a-t-il un bon / pratique d'algorithme pratique avec ce genre de complexité?

Et aussi, pour vérifier ma compréhension de la complexité algorithmique, sont ces deux $> o (n \ log (n) $) $

Je commence juste avec ce sujet et je ne suis vraiment sûr que si je le fais bien.

Merci et rester en sécurité.

Answer 1

$ o (\ journal n ^ n) $ et $ o (\ journal n!) $ Les deux décrivent le même ensemble de fonctions.

Notez que $ (\ frac {n} {e}) ^ n \ le n!\ le n ^ n $ et donc:

$ O (n \ journal n)= O (n \ journal \ frac {n} {e})= O (\ log (\ frac {n} {e}) \ n) \ sous -éréeq o (\ journal n!) \ Substeq o (\ journal n ^ n)= O (n \ journal n) $ .

Ceci montre que tous les ensembles ci-dessus coïncident.

Answer 2

$ n ^ n $ est beaucoup plus grand que n !. Le premier multiplie N x x n x N x ... x N (N fois), ce dernier multiplie 1 x 2 x 3 x 4 x ... x n. Il est donc évident que $ o (\ log (n ^ n)) n'est pas vrai. $ o (\ journal (n ^ n))> o (\ journal (n!)) $ est moins évident, mais pas vrai.

C'est parce que nous prenons le logarithme des deux côtés. Prendre des logarithmes change de produits aux sommes et aux exposants aux produits (très grossièrement). Et si nous prenons le produit pour N!, Il est évident que nous avons des facteurs N / 2 supérieurs à N / 2, donc n! > $ (n / 2) ^ {n / 2} $ . Prendre le logarithme, log n! > (n / 2) journal (n / 2). Pour n> 4, nous avons n / 2> $ n ^ {1/2} $ , donc log n / 2> (journal n) / 2, alors log n ! > (n / 2) journal (n / 2)> n / 4 journal n= 1/4 journal $ n ^ n $ .

alors log n!= $ \ theta (\ journal n ^ n) $ .