Número exacto de comparaciones para calcular la mediana

Volumen III de Knuth de The Art of Computer Programming (capítulo 5, verso 3.2) incluye la siguiente tabla que enumera el exacto número mínimo de comparaciones requeridas para seleccionar el -ésimo elemento más pequeño de un conjunto sin ordenar de tamaño , para todos . Esta tabla, junto con las conocidas expresiones de forma cerrada y , representa la mayor parte del estado del arte a 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$

Tabla de Knuth III: 5.3.2

¿Se han calculado más valores exactos de en los últimos 36 años? Estoy particularmente interesado en los valores exactos de , el número mínimo de comparaciones requeridas para calcular la mediana. $V_t(n)$ $M(n) = V_{\lceil n/2 \rceil}(n)$

Como señala @ MarkusBläser, la tabla de Knuth ya parece incorporar resultados más recientes de Bill Gasarch, Wayne Kelly y Bill Pugh ( Encontrando el i-ésimo más grande de n para los pequeños i, n . SIGACT News 27 (2): 88-96, 1996 .)

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

El artículo más famoso sobre el tema, creo, es el de Pratt y Yao (1976), a quienes se les atribuye estar entre los primeros en haber encontrado alguna técnica (de confrontación) para demostrar límites más bajos en este problema. Si tuviera que encontrar documentos recientes sobre el tema, seguiría las citas hechas a este documento . El artículo más reciente es el de Dor y Zwick, pero también hay una encuesta de 1996 realizada por Paterson (aunque no he buscado ver si se trata de resultados exactos o no).

Jérémie

Nitpicking: en la última oración de la pregunta, probablemente se refería al techo en lugar del piso.

Tsuyoshi Ito

Jeff, curioso por qué estás interesado en la respuesta exacta.

Chandra Chekuri

Kenneth Oksanen escribió un código eficiente para calcular . Desafortunadamente, solo hay un resumen disponible sciencedirect.com/science/article/pii/S1571065306001582 Hace dos años, uno de mis estudiantes le envió un correo electrónico y recibió el código. No recuerdo si se pudieron obtener algunos valores nuevos.

V_{i} (n)

$V_i(n)$

Markus Bläser

@ChandraChekuri: Estoy jugando con variantes del algoritmo de selección de tiempo lineal Blum-Floyd-Pratt-Rivest-Tarjan , como un problema potencial de tarea de algoritmos. Si usamos el algoritmo de comparación mínima para encontrar la mediana en cada bloque, entonces, ¿qué tamaño de bloque nos da la mejor constante en el gran Oh? 9 es mejor que 7 es mejor que 5; ¿Qué hay de 11?

Jeff el

Respuestas:

Kenneth Oksanen ha publicado una tabla ampliada de valores hasta , basada en su propia búsqueda en la computadora . Okansen también proporciona descripciones de los árboles de comparación óptimos para la mayoría de los valores que informa. Aquí hay una captura de pantalla de su mesa: $n=15$

Los límites de Kenneth Oksanen para la selección

¡Gracias a @ MarkusBläser por el liderazgo!

Jeffε
fuente

Me pregunto si esta información podría serle útil. Desafortunadamente, no proporciona ninguna información adicional a la pregunta de esta publicación, sino que responde más bien a su comentario sobre para qué sirve (análisis de variantes de QuickSelect).

El número mínimo esperado de comparaciones, observado o es, por supuesto, significativamente más fácil de calcular (con la expectativa tomada uniformemente en todas las permutaciones), $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.}.$

Este resultado no se usa con poca frecuencia y, en particular, es la base de los algoritmos en "Muestreo adaptativo para QuickSelect" de Martínez, Panario y Viola . El punto de partida del artículo es QuickSelect mediana de tres, y luego preguntar: ¿es pertinente elegir sistemáticamente la mediana, cuando el elemento que buscamos tiene un rango relativo mucho más bajo que n / 2 o mucho más alto que n / 2 ?

En otras palabras, suponga que está buscando el -ésimo elemento en una lista de elementos, y está eligiendo su pivote de los grupos de elementos. En lugar de tomar la mediana ( ), tomará donde . Muestran que este algoritmo puede, para la elección correcta de ser prácticamente más eficiente que la variante mediana de tres. $k$ $n$ $m$ $m/2$ $\alpha m$ $\alpha = k/n$ $m$

Jérémie
fuente