- Médiane des médianes
-
Un algorithme linéaire dans le pire des cas de calcul du Nieme plus grand élément d'un tableau a été publié par Blum, Floyd, Pratt, Rivest et Tarjan en 1973 dans "Time bounds for selection", parfois appelé BFPRT d'après les noms des auteurs. Il est basé sur l'algorithme de tri rapide et connu aussi comme algorithme de calcul de la médiane des médianes.
Bien que le tri rapide soit sous-quadratique en temps, en moyenne, il peut exiger un temps quadratique lorsque le choix du pivot est mauvais (prenons le cas d'un pivot égal au plus petit élément à chaque étape). La solution pour le rendre O(n log(n)) dans le pire des cas est de toujours trouver des "bons" pivots. Un bon pivot est celui pour lequel on peut établir qu'une proportion constante d'éléments situés au-dessous et au-dessus.
Sommaire
Algorithme
L'algorithme est en 3 étapes :
- L'algorithme divise la liste en groupes de cinq éléments. Ensuite, pour chaque groupe de cinq, la médiane est calculée (une opération qui peut s'effectuer en temps constant).
- L'algorithme est alors appelée récursivement sur cette sous-liste de N/ 5 éléments pour trouver la vraie médiane de ces éléments.
- Enfin, la médiane des médianes est choisi pour être le pivot. Selon la position de l'élément recherche, l'algorithme recommence avec les éléments au dessus du pivot ou au dessous.
Propriétés du pivot
Le pivot choisi est à la fois inférieur à environ 3 (n/10) éléments et plus grand que 3 (n/10) éléments. Ainsi, la médiane divise les éléments choisis quelque part entre 30% / 70% et 70% / 30%, ce qui assure dans le pire des cas un comportement linéaire de l'algorithme. Pour visualiser:
Une itération des deux premières étapes de l'algorithme sur {0,1,2,3,...99} 12 15 11 2 9 5 0 7 3 21 44 40 1 18 20 32 19 35 37 39 13 16 14 8 10 26 6 33 4 27 49 46 52 25 51 34 43 56 72 79 Médianes 17 23 24 28 29 30 31 36 42 47 50 55 58 60 63 65 66 67 81 83 22 45 38 53 61 41 62 82 54 48 59 57 71 78 64 80 70 76 85 87 96 95 94 86 89 69 68 97 73 92 74 88 99 84 75 90 77 93 98 91 En rouge, la médiane des médianes.
Preuve du O(n)
T(n) ≤ T(n/5) + T(7n/10) + O(n)
D'où T(n) ≤ c*n*(1 + (9/10) + (9/10)2 + ...) = O(n).
Remarque importante
Bien que cette approche fonctionne très bien en théorie, elle est souvent dépassée dans la pratique par l'algorithme utilisant des pivots aléatoires.
Notes et références
Catégorie :- Vocabulaire des mathématiques
Wikimedia Foundation. 2010.
