Algorithmique Avancée: Tri, Recherche et Complexité

Correction :

Quand $n$ est multiplié par 10, le temps est multiplié par $10$ en $\Theta(n)$, par $10^2 = 100$ en $\Theta(n^2)$, et par $\dfrac{10^5 \log 10^5}{10^4 \log 10^4} = 10 \times \dfrac{5}{4} = 12{,}5$ en $\Theta(n\log n)$.

Résultat : 20 s en $\Theta(n)$, 25 s en $\Theta(n\log n)$, 200 s en $\Theta(n^2)$.

Correction :

Chaque passage échange le minimum de la partie non triée avec sa première case.

passage 1 : [11, 25, 12, 22, 64]
passage 2 : [11, 12, 25, 22, 64]
passage 3 : [11, 12, 22, 25, 64]
passage 4 : [11, 12, 22, 25, 64]

Trouver le minimum de $k$ éléments coûte $k - 1$ comparaisons : $4 + 3 + 2 + 1 = 10$.

Résultat : 10 comparaisons, et $\dfrac{n(n-1)}{2}$ pour $n$ éléments, quel que soit l'ordre de départ.

Correction :

Chaque passage pousse le plus grand élément restant vers la fin.

passage 1 : [1, 4, 2, 5, 8]   (3 échanges)
passage 2 : [1, 2, 4, 5, 8]   (1 échange)
passage 3 : aucun échange, tableau trié, arrêt

Résultat : 3 passages, contre $n - 1 = 4$ pour la version sans arrêt.

Correction :

a) Les cases sont testées dans l'ordre : 4 comparaisons pour 42, la quatrième case ; 7 pour 99, absent.

b) Une valeur en position $k$ coûte $k$ comparaisons. En moyenne : $\dfrac{1 + 2 + \dots + n}{n} = \dfrac{n+1}{2}$, soit 4 pour $n = 7$.

Résultat : 4 et 7 comparaisons ; $\dfrac{n+1}{2}$ en moyenne, soit 4 ici. Le cas moyen reste en $\Theta(n)$.

Correction :

À chaque tour, on garde la moitié qui peut encore contenir la valeur.

recherche de 70
debut=0 fin=8 milieu=4   50 trop petit
debut=5 fin=8 milieu=6   trouvé
recherche de 25
debut=0 fin=8 milieu=4   50 trop grand
debut=0 fin=3 milieu=1   20 trop petit
debut=2 fin=3 milieu=2   30 trop grand
debut=2 fin=1            arrêt, absent

Résultat : 70 trouvé à l'indice 6 en 2 tours ; 25 absent, constaté en 3 tours. Erreur à éviter : s'arrêter quand $\text{debut} = \text{fin}$, alors qu'il reste une case à tester.

Correction :

Compter les tours, puis garder le terme dominant.

a) $n \times n = n^2$ tours : $\Theta(n^2)$.

b) Pour chaque $i$, la boucle sur $j$ fait $i + 1$ tours : $1 + 2 + \dots + n = \dfrac{n(n+1)}{2}$. Diviser par 2 ne change pas l'ordre de grandeur : $\Theta(n^2)$.

c) Après $k$ tours, $i = 2^k$ ; la boucle s'arrête dès que $2^k \geq n$, soit après $\lceil \log_2 n \rceil$ tours : $\Theta(\log n)$.

Résultat : $\Theta(n^2)$, $\Theta(n^2)$ et $\Theta(\log n)$. Ce sont les tours qui comptent, pas les boucles écrites.

Correction :

Pour $k$ recherches, on compare les deux stratégies.

a) Linéaire : $10^6$. Dichotomie : $2^{19} = 524\,288 \leq 10^6 < 2^{20}$, donc $\lfloor \log_2 10^6 \rfloor + 1 = 20$.

b) Sans tri : $k \times 10^6$. Avec tri : $10^6 \log_2 10^6 + 20k \approx 2 \times 10^7 + 20k$. Trier gagne quand $10^6 k > 2 \times 10^7 + 20k$, soit $k > \dfrac{2 \times 10^7}{10^6 - 20} \approx 20$.

Résultat : $10^6$ contre 20 comparaisons ; trier d'abord devient rentable vers 20 recherches. Pour une seule recherche, c'est une perte : $n\log n$ dépasse $n$.

Correction :

L'élément remonte tant que son voisin de gauche est plus grand ; chaque test est une comparaison.

insérer 11 : 1 comparaison    [11, 12, 13, 5, 6]
insérer 13 : 1 comparaison    [11, 12, 13, 5, 6]
insérer 5  : 3 comparaisons   [5, 11, 12, 13, 6]
insérer 6  : 4 comparaisons   [5, 6, 11, 12, 13]

Total : $1 + 1 + 3 + 4 = 9$. Meilleur cas (déjà trié) : $n - 1 = 4$ ; pire cas (trié à l'envers) : $\dfrac{n(n-1)}{2} = 10$.

Résultat : 9 comparaisons, entre 4 et 10. Erreur à éviter : comparer aussi 13 à 11, alors que $13 > 12$ arrête déjà la boucle.

Correction :

On traduit le code en récurrence et on la déroule.

a) $M(0) = 0$ et, pour $n \geq 1$, $M(n) = M(n-1) + 1$ : une multiplication, plus celles de l'appel sur $n - 1$. Donc $M(n) = n$, et le temps est en $\Theta(n)$.

b) Au plus profond, les $n + 1$ appels, de factorielle(n) à factorielle(0), attendent tous sur la pile d'appels (la mémoire réservée aux appels en cours). La mémoire est en $\Theta(n)$, contre $\Theta(1)$ pour une boucle.

Résultat : $M(n) = n$ ; temps en $\Theta(n)$ ; mémoire en $\Theta(n)$ en récursif, $\Theta(1)$ avec une boucle.

Correction :

a) Initialisation, $k = 0$ : $T(1) = 0 = 0 \times 2^0$. Hérédité : si $T(2^{k-1}) = (k-1)\,2^{k-1}$, alors $T(2^k) = 2(k-1)\,2^{k-1} + 2^k = (k-1)\,2^k + 2^k = k\,2^k$. Avec $1024 = 2^{10}$ : $T(1024) = 10 \times 1024 = 10\,240$.

b) Sur un tableau trié, le pivot est le plus petit élément : une partie est vide, l'autre garde les $n - 1$ éléments suivants, encore triés. Le scénario se répète : $(n-1) + (n-2) + \dots + 1 = \dfrac{n(n-1)}{2}$ comparaisons, en $\Theta(n^2)$. Pour $n = 1024$ : $\dfrac{1024 \times 1023}{2} = 523\,776$.

Résultat : $10\,240$ comparaisons au plus pour le tri fusion, $523\,776$ pour ce tri rapide. Le camarade a tort : le tri rapide est en $\Theta(n\log n)$ en moyenne, pas dans le pire cas. Un pivot tiré au hasard rend ce cas très improbable.