Ordres de grandeur — exercice corrigé d'algorithmique (école d'ingénieur) (chapitre 10)

Ordres de grandeur

Complexité des programmes · niveau 1 (application)

Énoncé

Classer les fonctions suivantes par ordre de croissance : $n^{2}$ , $n$ , $2^{n}$ , $n lo g n$ , $lo g n$ , $100 n$ , $n^{3}$ , $n!$ , $1, 0 1^{n}$ , $n^{2} lo g n$ , $lo g (n^{2})$ . Indiquer celles qui ont le même ordre de grandeur.

Corrigé

Par ordre de croissance :

$lo g n \equiv lo g (n^{2}) ≪ n ≪ 100 n ≪ n lo g n ≪ n^{2} ≪ n^{2} lo g n$

$n^{2} lo g n ≪ n^{3} ≪ 1, 0 1^{n} ≪ 2^{n} ≪ n!$

$lo g (n^{2}) = 2 lo g n$ : c'est le même ordre de grandeur que $lo g n$ (les constantes multiplicatives ne comptent pas). Ce sont les deux seules fonctions de la liste qui ont le même ordre de grandeur.
$100 n \in Θ (n)$ : malgré la constante $100$ , la fonction $n lo g n$ finit par la dépasser (dès que $lo g_{2} n > 100$ ).
Toute exponentielle $a^{n}$ avec $a > 1$ , même $1, 0 1^{n}$ , finit par dépasser tout polynôme : $n^{3} /1, 0 1^{n} \to 0$ . Mais il faut attendre : $1, 0 1^{n}$ ne dépasse $n^{3}$ qu'au-delà de $n \approx 2300$ .
$2^{n} ≪ n!$ car $n! / 2^{n} = \prod_{i = 1}^{n} (i /2)$ et chaque facteur au-delà du troisième est supérieur à $1, 5$ .