Explication de la Médiane des Médianes de l'algorithme

La Median of medians approche est très populaire dans quicksort type de partitionnement des algorithmes pour produire un assez bon pivot, tels qu'il les partitions de la matrice de manière uniforme. Sa logique est donnée dans Wikipédia:

Choisi de pivot est à la fois moins et plus de la moitié des éléments dans la liste des médianes, qui est d'environ n/10 éléments (1/2 * (n/5)) pour chaque semestre. Chacun de ces éléments est une médiane de 5 moins de 2 autres éléments, et de plus de 2 autres éléments à l'extérieur du bloc. Par conséquent, le pivot est à moins de 3(n/10), les éléments à l'extérieur du bloc, et plus grand qu'un autre 3(n/10), les éléments à l'extérieur du bloc. Ainsi, la choisi la médiane divise les éléments quelque part entre 30%/70% et 70%/30%, ce qui assure les pires cas de comportement linéaire de l'algorithme.

Quelqu'un peut-il expliquer un peu de lucidité pour moi. Je trouve qu'il est difficile de comprendre la logique.

OriginalL'auteur SexyBeast | 2012-09-22

  1. 14

    Pense de l'ensemble des nombres:

    5 2 6 3 1

    La médiane de ces nombres est 3. Maintenant, si vous avez un certain nombre n, si n > 3, alors il est plus grand que la moitié au moins de l'un des numéros ci-dessus. Si n < 3, alors il est plus petit que la moitié au moins de l'un des numéros ci-dessus.

    De sorte que c'est l'idée. C'est, pour chaque série de 5 numéros, vous obtenez leur médiane. Maintenant, vous avez n /5 numéros. Cela est évident.

    Maintenant, si vous obtenez la moyenne de ces nombres (appeler 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 des nombres (qui étaient eux-mêmes les médianes de petit 5 groupes d'éléments) et plus grand que l'autre n /10 numéros (qui ont été de nouveau médianes des petits de 5 groupes d'é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 aussi plus grande que les 2 autres nombres (qui étaient eux-mêmes plus petits que k). Cela signifie que pour chacune de ces plus petits de 5 groupes d'élément où m était plus grand que son support, m est plus grand aussi de deux autres nombres. Cela en fait au moins 3 numéros (2 numéros + la médiane elle-même) dans chacun de ces n /10 petit 5 groupes d'éléments, qui sont plus petits que m. Par conséquent, m est au moins plus grand que 3n/10 numéros.

    Logique similaire pour le nombre d'éléments m est plus grand que.

    Juste une autre question, comment fonctionne cette méthode garantit que ce nombre sera la médiane? La médiane est un nombre qui partitionne le tableau dans la partie supérieure et la moitié inférieure. Alors qu'est-ce 30-30-70 figure signifier?
    Ainsi, la médiane est dans le milieu, mais m (dans le texte ci-dessus) n'est pas de la médiane de tous les numéros. C'est la médiane de seulement 1/5 des nombres (qui sont eux-mêmes des médianes des petits de 5 groupes d'éléments). Essayez de lire le dernier paragraphe avec plus d'attention. À la fin, où il est conclu que m est plus grand que au moins 3n/10 des nombres, bien que se traduit par m est plus grand qu'au moins 30% des effectifs. Donc en fin de compte, il va comme m est plus grand qu'au moins 30% et inférieure à au moins un autre 30%. Il est de 40% à gauche, dont nous ne sommes pas sûr de.
    Alors comment se fait-il donne un 50-50 partition en moyenne? Le 50-50 partition est donnée par la normale médiane, à droite?
    Il ne donne pas de 50-50 partition en moyenne. Il donne toujours quelque part entre 30-70 et 70-30 (peut-être que vous pourriez appeler que 50-50 en moyenne?), mais ce n'est pas le point. Pour quicksort pour donner O(nlogn) temps de la complexité, il doit être capable de diviser le tableau en partitions proportionnelle à la taille de la matrice. C'est ce qui donne la logn profondeur de récursion. 30-70 division donne déjà une 3n/10 et 7n/10 division qui est proportionnelle à n. Donc même si c'est pas parfait 50-50, il reste toujours le rendement logarithmique de la profondeur de récursion (sauf que c'est pas log en base 2, mais la base de 10/7)

    OriginalL'auteur Shahbaz

  2. 3

    Explication de la médiane - de - médianes algorithme pour trouver la k-ième plus grand entier de n peuvent également être trouvés ici: http://cs.indstate.edu/~spitla/présentation.pdf

    OriginalL'auteur totjammykd