Exercice 1

On considère le programme suivant, qui calcule {$n^p$} :

Calculer la coimplexité de cet algorithme en nombre de multiplications dans le meilleur et dans le pire des cas.

Exercice 2 : Analyse de l'algorithme du tri rapide

L'algorithme du tri rapide pour classer les éléments d'un tableau tab situés entre les indices min et max inclus est :

Cet algorithme consiste à mettre un élément particulier, le pivot, à la place qu'il aurait dans le tableau classé, en déplaçant tous les éléments qui lui sont inférieurs ou égaux à sa gauche, et tous ceux qui lui sont supérieurs à sa droite. Si p est la position du pivot, il ne reste ensuite qu'à appliquer de nouveau l'algorithme au sous-tableau de droite (entre min et p-1) et au sous-tableau de droite (entre p+1 et max).

L'appel de tri_rapide(tab, 0, n-1) trie tous les éléments du tableau s'il est de taille n.

L'opération partition est celle qui réalise effectivement le tri lors des appels récursifs à tri_rapide :

La configuration des éléments du tableau lors du test de l'élément d'indice k est indiquées sur la figure suivante :

Le symbole • indique le pivot, les symboles ≤ et > indiquent des éléments respectivement inférieurs ou égaux et strictement supérieurs au pivot. Le symbole ? indique des éléments dont on ne connait pas encore la position par rapport au pivot.

Question 1

Calculez la complexité en nombre de comparaisons d'éléments du tableau de l'algorithme de partition.

Question 2

Calculez la complexité en moyenne {$M(n)$} (en nombre de comparaisons d'éléments du tableau) de l'algorithme du tri rapide pour un tableau de taille {$n$}.

Montrez que cette complexité vérifie : {$${\displaystyle M(n) = n-1+\frac{1}{n} \sum_{p=1}^{n}\left(M(p-1) + M(n-p)\right)}$$}