Explication de la Médiane des Médianes de l'algorithme
l'approche Median of medians est très populaire dans les algorithmes de partitionnement de type quicksort pour produire un assez bon pivot, de sorte qu'il cloisonne le tableau uniformément. Sa logique est donnée dans Wikipedia comme:
le pivot choisi est à la fois inférieur et supérieur à la moitié des éléments de la liste des médianes, qui est d'environ n/10 éléments (1/2 * (n/5)) pour chaque moitié. Chacun de ces éléments est une médiane de 5 moins de 2 autres éléments et plus que 2 autres éléments à l'extérieur du bloc. Par conséquent, le pivot est inférieur à 3(n/10) éléments à l'extérieur du bloc et supérieur à 3(N/10) autres éléments à l'extérieur du bloc. Ainsi, la médiane choisie divise les éléments entre 30%/70% et 70%/30%, ce qui assure le comportement linéaire du pire cas de l'algorithme.
est-ce que quelqu'un peut l'expliquer un peu lucidement pour moi. Je trouve qu'il est difficile de comprendre la logique.
2 réponses
pensez aux nombres suivants:
5 2 6 3 1
La médiane de ces nombres est 3 . Maintenant, si vous avez un nombre n , si n > 3 , alors il est plus grand qu'au moins la moitié des nombres ci-dessus. Si n < 3 , alors il est plus petit qu'au moins la moitié des nombres ci-dessus.
donc c'est l'idée. C'est, pour chaque série de 5 numéros, vous obtenez leur médiane. Maintenant, vous avez les numéros n / 5 . C'est évident.
maintenant si vous obtenez la médiane de ces numéros (appelez-le m ), il est plus grand que la moitié d'entre eux et plus petit que l'autre moitié (par définition de la médiane!). En d'autres termes, m est plus grand que n / 10 nombres (qui étaient eux-mêmes médians de petits groupes de 5 éléments) et plus grand qu'un autre n / 10 nombres (qui étaient encore médians de petits groupes de 5 éléments).
Dans l'exemple ci-dessus, nous avons vu que si la médiane est k et vous avez m > k , puis m est également plus grand que 2 autres numéros (qui étaient eux-mêmes plus petits que k ). Cela signifie que pour chacun des groupes de 5 éléments plus petits où m était plus grand que son milieu, m est plus grand aussi que deux autres nombres. Cela fait au moins 3 Nombres (2 nombres + la médiane elle-même) dans chacun de ces n / 10 Petits 5 groupes d'éléments, qui sont plus petits que m . Par conséquent, m est à au moins plus grand que le nombre 3n/10 .
logique similaire pour le nombre d'éléments m est plus grand que.
explication de l'algorithme de la médiane des médianes pour trouver le k-ème plus grand entier de n peut également être trouvé ici: http://cs.indstate.edu/~spitla / presentation.pdf