étant donné 5 chiffres, quel est le nombre minimum de comparaisons nécessaires pour trouver la médiane?

Question

comment voulez-vous nombre minimum d'installation des comparaisons en général?

Answer 1

Pour citer Donald Knuth (par voie de Wikipédia, puisque je n'ai pas ma copie de TAOCP au moment), la limite inférieure pour le nombre de comparaisons est six:

http://en.wikipedia.org/wiki/Selection_algorithm (faites défiler jusqu'à la section intitulée "Lower Bounds").

Votre but est, effectivement, pour trouver les k valeurs les plus basses où k est la moitié de la taille de la liste, arrondie, (donc, k = 3; n = 5), puis prendre le maximum de ceux-ci. Que dans la brancher formule là sur la page, vous obtenez:

(5 - 3) + 1 + 1 + 2 = 6

Dans ce cas, le minimum réel nombre de comparaisons nécessaires est également six .

Si vous êtes dans le doute que la tâche de trouver la médiane est aussi difficile que de trouver k valeurs les plus faibles, vous pouvez vous référer à TAOCP Knuth, le volume 3, excercise # 2 après 5.3.3 chapitre.

Answer 2

Il y a beaucoup de matériel à ce sujet dans le volume 3 de Donald Knuth L'art de la programmation informatique , dans la section 5.3.3, -Comparaison minimum Sélection , où la question plus générale du nombre minimum de comparaisons nécessaires pour sélectionner le t e plus grand de n valeurs est considéré. (Cette valeur est désignée par V _t (n) ).

Knuth donne une limite supérieure de n - t + (t-1) ⌈lg (n + 2 - t) ⌉ pour V _t (n ) , réalisé en déterminant d'abord le plus grand élément de n - t + 2 par un système de tournoi, suppression de cette (car il ne peut pas être t e plus grand) et le remplacer par l'un des éléments restants, la poursuite de cette procédure jusqu'à ce que tous les éléments ont été une partie de cette procédure, et le plus important élément à ce stade est le t e plus grand de l'ensemble original. Dans ce cas, n = 5 et t = 3 , de sorte que la limite supérieure donnée par cette formule est de 6 comparaisons.

Knuth mentionne que cela est exact lorsque la limite supérieure n ≤ 6 , de sorte que applique dans ce cas. En général, je crois comprendre qu'il n'y a pas de procédures générales pour trouver des algorithmes minimum de comparaison pour la sélection (et le tri) et les enregistrements pour les valeurs de plus en plus n utilisent généralement des tours spéciaux qui ne sont pas applicables en général des valeurs plus élevées ou sont simplement passés à tabac par d'autres tours lorsque n augmente.