Que vaut log ₂(n!) ? La borne, au plus près — exercice corrigé d'informatique (tronc commun des prépas scientifiques) (chapitre 9)

Que vaut

lo g_{2} (n!)

? La borne, au plus près

Les tris · niveau 3 (difficile)

É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).

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

Énoncé

Corrigé

Exercices semblables

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