Que vaut $lo g_{2} (n!)$ ? La borne, au plus près

Exercice · informatique (tronc commun des prépas scientifiques), chapitre 9 — Les tris

Énoncé

Minorer $lo g_{2} (n!)$ pour estimer le nombre minimal de comparaisons nécessaires pour trier 100 éléments.

Corrigé

En séparant le produit en deux : les $n /2$ plus grands termes sont minorés par $n /2$ . $n! \geq (\frac{n}{2})^{n /2} ⟹ lo g_{2} (n!) \geq \frac{n}{2} lo g_{2} (\frac{n}{2})$ Pour $n = 100$ , le calcul exact donne $lo g_{2} (100!) \approx 525$ comparaisons. Le tri fusion réalise au maximum $100 \times ⌈ lo g_{2} 100 ⌉ - 2^{⌈ l o g_{2} 100 ⌉} + 1 = 100 \times 7 - 128 + 1 = 573$ comparaisons, ce qui est extrêmement proche de l'optimalité théorique absolue (à moins de 10 % près).

Les autres exercices de ce chapitre Le cours du chapitre

Un blocage sur cet exercice ? Le tuteur d'Adloun guide par questions, sans donner la réponse.

Que vaut log2​(n!) ? La borne, au plus près

Énoncé

Corrigé

Que vaut $lo g_{2} (n!)$ ? La borne, au plus près