Exercice 1

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

operation puissance: int n, int p → int
  int x ← n
  int y ← p
  int r ← 1
  tant_que y ≠ 0 faire
    si y impair alors
      y ← y - 1
      r ← r * x
    fin_si
    x ← x * x
    y ← y ÷ 2
  fin_tant_que
  résultat ← r
fin_operation

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 :

operation tri_rapide: int[] tab, int min, int max →
  si min < max alors
    p ← partition(tab, min, max)
    tri_rapide(tab, min, p-1)
    tri_rapide(tab, p+1, max)
  fin_si
fin_operation

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 :

operation partition: int[] tab, int min, int max) →
  int p = min
  int pivot = tab[p]

  pour int k variant de min+1 à max faire
    si tab[k] < pivot alors
      // si l'élément d'indice k devrait se trouver à gauche du pivot
      // on le met à la place actuelle du pivot
      tab[p] ← tab[k]
      // on le remplace par un élément ≤ pivot
      tab[k] ← tab[p+1]
      // on met le pivot à la place de l'élément qui a remplacé l'élément mal placé
      tab[p+1] ← pivot
      // et on met à jour la position du pivot
      p ← p+1
    fin_si
  fin_pour
 résultat ← p
fin_operation

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)}$$}