¿Cuál es el menor número de comparaciones que necesita para encontrar la mediana de 6 distintos números?
Soy capaz de encontrar la respuesta a la mediana de los 5 diferentes números 6 comparaciones, y tiene sentido, sin embargo, en el caso de los 6 números que no puede encontrar una respuesta.
El mejor yo era capaz de hacer en la mano, fue el 9 de comparaciones. Esto puede ser minimizado?
Edit: la Mediana en este caso, estamos suponiendo ser el más bajo promedio.
Toma por lo menos 8 y se puede hacer exactamente 8.
EDITAR
Como se ha señalado por hardmath, el límite inferior de abajo es en realidad un superior límite en el límite inferior. JeffE notas que me enlace en la parte inferior dar un valor de $7$, no $8$.
Ver este cstheory pregunta aquí (de nuevo gracias a hardmath): http://cstheory.stackexchange.com/questions/12257/exact-number-of-comparisons-to-compute-the-median/12287#12287
que de hecho dicen que el valor es $8$.
Nota: la siguiente es una prueba incompleta.
Límite Inferior
Un límite inferior para encontrar todas las $k$ elementos más pequeños se dan aquí: límites Inferiores de la Selección.
El que dice que necesitamos al menos
$$ n - k + \sum_{n+1-k < j \le n} \lceil \log_{2} j \rceil $$
Para $n=6, k=3$, esto le da a $9$.
$$ 6 - 3 + \lceil \log_{2} 5 \rceil + \lceil \log_{2} 6 \rceil = 9$$
Por lo tanto para encontrar el más pequeño, el segundo más pequeño y el tercero, más pequeño, necesitamos al menos $9$ compara.
Ahora, cualquier algoritmo que encuentra el $3^{rd}$ elemento más pequeño (es decir $z$), se tiene que encontrar el conjunto $S = \\{x, y \\}$ tal que $x < z$ $y < z$ (de lo contrario, ¿cómo saber que $z$ es la tercera más grande?).
Un extra de comparar entre $x$ $y$ nos dará ahora el más pequeño, el segundo más pequeño y el tercero más pequeño de los números.
Por lo tanto, cualquier algoritmo que encuentra el tercer menor deben utilizar al menos 8 de las comparaciones.
Límite Superior
Como I. J. Kennedy notas, existe un algoritmo para encontrar el 3er elemento más pequeño de 6 elementos en 8 comparaciones y se puede encontrar en Knuth del Arte de la Programación de computadoras Vol 3, Página 212.
De acuerdo a Knuth, este es un resultado obtenido por A. Hadian y M. Sobel [Universidad de Minnesota, en el Departamento de Estadística Informe 121 (169)] y muestran que la $k^{th}$ mayor elemento se puede encontrar en
$$ n - k + (k-1) \lceil \log_{2} (n+2-k) \rceil $$
las comparaciones. Para $n=6$ $k=4$ obtenemos el límite superior de $8$.
Algoritmo
La manera en que lo hacen (Knuth del libro tiene toda esta información) es:
Crear en primer lugar un torneo de eliminatoria en $n-k+2$ elementos, que se lleva a $n-k+1$ compara.
El elemento más grande (es decir $L$) de esto no puede ser candidato. Así del resto de las $k-2$ elegir uno y seguir el camino de $L$ hasta el árbol, que da la nueva más grande en la mayoría de los $\lceil \log_{2} n+2-k \rceil$ compara. Quitar este nuevo más grande, reemplazándolo con uno de los restantes y el seguimiento de la ruta de esta nueva más grande.
Continuar hasta que el resto de la $k-2$ están agotadas. Por último, sustituir la más grande, con $-\infty$ y determinar el más grande de los restantes $n+1-k$ que será el $k^{th}$ más grande que hemos eliminado la mayor $k-1$ hasta la fecha.
Relacionado con: http://compgeom.cs.uiuc.edu/~jeffe/enseñanza/497/02-selección.pdf
Parece que la respuesta es 8.
Mi Knuth Volumen Tres (1970—no tan polvoriento como usted piensa) informa de un límite superior de 8, que, junto con el Imbécil del límite inferior de 8, ...
La forma general de esta cuestión se llama la Selección del Problema. Si buscas en google la frase que usted tendrá un montón de resultados de utilidad.
Edit: Knuth no dar una explícita algoritmo para encontrar la mediana de 6 elementos en la mayoría de los 8 pasos (al menos en la primera edición). Sin embargo, en el ejercicio 12 de la sección 5.3.3, le da el método explícito para encontrar la mediana de 7 elementos, utilizando en la mayoría de los 10 comparaciones, que puede ser de alguna ayuda.
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
