Nombre exact de comparaisons pour calculer la médiane

Le volume III de The Art of Computer Programming de Knuth (chapitre 5, verset 3.2) comprend le tableau suivant répertoriant le nombre minimum exact de comparaisons nécessaires pour sélectionner le ème plus petit élément à partir d'un ensemble non trié de taille , pour tous les . Ce tableau, avec les expressions bien connues de forme fermée et , représente l' essentiel de l'état de l'art à partir de 1976 . $t$ $n$ $1\le t \le n\le 10$ $V_1(n) = n-1$ $V_2(n) = n - 2 + \lceil n/2 \rceil$

Tableau de Knuth III: 5.3.2

Des valeurs plus exactes de été calculées au cours des 36 dernières années? Je suis particulièrement intéressé par les valeurs exactes de , le nombre minimum de comparaisons nécessaires pour calculer la médiane. $V_t(n)$ $M(n) = V_{\lceil n/2 \rceil}(n)$

Comme le souligne @ MarkusBläser, le tableau de Knuth semble déjà intégrer des résultats plus récents de Bill Gasarch, Wayne Kelly et Bill Pugh ( Trouver le ième plus grand de n pour les petits i, n . SIGACT News 27 (2): 88-96, 1996 .)

ds.algorithms reference-request co.combinatorics sorting selection Jeffε
la source

Le document le plus célèbre sur le sujet, je pense, est celui de Pratt et Yao (1976), qui sont réputés être parmi les premiers à avoir trouvé une technique (contradictoire) pour prouver les limites inférieures de ce problème. Si je devais trouver des articles récents sur le sujet, je suivrais les citations faites à cet article . L'article le plus récent est celui de Dor et Zwick, mais il y a aussi une enquête de 1996 de Paterson (bien que je n'aie pas cherché à voir si elle se préoccupe des résultats exacts ou non).

Jérémie

Nitpicking: Dans la dernière phrase de la question, vous parliez probablement du plafond au lieu du sol.

Tsuyoshi Ito

Jeff, curieux de savoir pourquoi vous êtes intéressé par la réponse exacte.

Chandra Chekuri

Kenneth Oksanen a écrit un code efficace pour calculer . Malheureusement, il n'y a qu'un résumé disponible sciencedirect.com/science/article/pii/S1571065306001582 Il y a deux ans, un de mes étudiants lui a envoyé un e-mail et a obtenu le code de lui. Je ne me souviens pas si de nouvelles valeurs pourraient être obtenues.

V_{i} (n)

$V_i(n)$

Markus Bläser

@ChandraChekuri: Je joue avec des variantes de l' algorithme de sélection du temps linéaire Blum-Floyd-Pratt-Rivest-Tarjan , comme un problème potentiel de devoirs des algorithmes. Si nous utilisons l'algorithme de comparaison minimale pour trouver la médiane dans chaque bloc, alors quelle taille de bloc nous donne la meilleure constante dans le grand Oh? 9 vaut mieux que 7 vaut mieux que 5; qu'en est-il de 11?

Jeffε

Je me demande si cette information pourrait vous être utile. Malheureusement, il ne fournit aucune information supplémentaire à la question de ce message, mais répond plutôt à votre commentaire sur ce à quoi il servait (analyse des variantes de QuickSelect).

$v(n,t)$ $v_t(n)$

v_{t} (n) = n + min (t, n - t) + l.o.t. .

$v_t(n)=n+\min(t,n-t)+\text{l.o.t.}.$

Ce résultat n'est pas rarement utilisé et constitue en particulier la base des algorithmes de "Adaptive Sampling for QuickSelect" de Martínez, Panario et Viola . Le point de départ de l'article est la médiane de trois QuickSelect, puis de se demander: est-il pertinent de choisir systématiquement la médiane, lorsque l'élément que nous recherchons a un rang relatif bien inférieur à n / 2 ou bien supérieur à n / 2 ?

En d'autres termes, supposons que vous recherchez le ème élément dans une liste de éléments, et que vous choisissez votre pivot parmi des clusters de éléments. Au lieu de prendre la médiane ( ), vous prendrez où . Ils montrent que cet algorithme peut, pour le bon choix de être pratiquement plus efficace que la variante médiane de trois. $k$ $n$ $m$ $m/2$ $\alpha m$ $\alpha = k/n$ $m$

Jérémie
la source

Nombre exact de comparaisons pour calculer la médiane

Réponses: