Comprendre l'algorithme "médiane des médianes"

Question

Salut, je veux comprendre "médiane des médianes" de l'algorithme sur l'exemple suivant:

Nous avons donc 45 distinctes chiffres divisés à 9 groupe avec 5 éléments.

48 43 38 33 28 23 18 13 8

49 44 39 34 29 24 19 14 9 

50 45 40 35 30 25 20 15 10

51 46 41 36 31 26 21 16 53

52 47 42 37 32 27 22 17 54

1. La première étape est le tri de chaque groupe (dans ce cas, ils sont déjà triés)

2. Deuxième étape, de manière récursive, trouver le "vrai" médiane des médianes (50 45 40 35 30 25 20 15 10), à savoir que le jeu sera divisé en 2 groupes:

   50 25
   
   45 20 
   
   40 15
   
   35 10
   
   30
   

   tri des 2 groupes

   30 10
   
   35 15 
   
   40 20
   
   45 25
   
   50
   

la valeur médiane est de 40 et 15 (dans le cas où les nombres sont de même nous avons pris à gauche de la médiane) si la valeur retournée est de 15 toutefois, la "vraie" médiane des médianes (50 45 40 35 30 25 20 15 10) est de 30, de plus il y a 5 éléments moins de 15 qui sont beaucoup moins que 30% de 45 qui sont mentionnés dans wikipedia

et donc, T(n) <= T(n/5) + T(7n/10) + O(n) d'échec.

Par la manière de wikipédia en exemple je reçois le résultat de la récursivité 36 cependant, le vrai médian est de 47 ans.

Je pense donc que, dans certains cas, cette récursivité peut pas retourner true médian des médianes. Je veux comprendre où est mon erreur.

Answer 1

Le problème, c'est l'étape où vous vous dites à trouver le vrai médiane de la médiane. Dans votre exemple, vous avez eu ces médianes:

50 45 40 35 30 25 20 15 10

Le vrai médian de l'ensemble de ces données est de 30 ans, pas 15. Vous ne trouvez pas ce médiane par diviser les groupes en blocs de cinq et en prenant la médiane de ces médianes, mais plutôt par l'appelant récursivement l'algorithme de sélection sur ce petit groupe. L'erreur dans votre logique est en supposant que la médiane de ce groupe est trouvé par le fractionnement de la séquence ci-dessus en deux blocs

50 45 40 35 30

et

25 20 15 10

puis la recherche de la médiane de chaque bloc. Au lieu de cela, la médiane-de-médianes algorithme récursivement appeler lui-même sur le jeu de données complet 50 45 40 35 30 25 20 15 10. En interne, cela permettra de scinder le groupe en blocs de cinq et de les trier, etc., mais il le fait pour déterminer la partition de point pour l'étape de partitionnement, et c'est dans cette étape de partitionnement que l'appel récursif trouverez le véritable médian des médianes, qui dans ce cas sera de 30. Si vous utilisez 30 comme la médiane que l'étape de partitionnement dans l'algorithme original, vous n'avez en effet d'obtenir une très bonne répartie comme requis.

Espérons que cette aide!

Answer 2

Vous ne vous arrêterez pas là, mais vous continuerez la récurrence, et après la fonction retournée pour 40 et 15, elle retournera au niveau supérieur.