Algoritmo de selección

Método para encontrar el k-ésimo valor más pequeño

En informática , un algoritmo de selección es un algoritmo para encontrar el valor más pequeño en una colección de valores ordenados, como números. El valor que encuentra se llama estadística de orden . La selección incluye como casos especiales los problemas de encontrar el elemento mínimo , mediano y máximo en la colección. Los algoritmos de selección incluyen selección rápida y el algoritmo de mediana de medianas . Cuando se aplican a una colección de valores, estos algoritmos toman tiempo lineal , como se expresa utilizando la notación O mayúscula . Para los datos que ya están estructurados, pueden ser posibles algoritmos más rápidos; como caso extremo, la selección en una matriz ya ordenada toma tiempo . ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle n}$ ${\displaystyle O(n)}$ ${\displaystyle O(1)}$

Planteamiento del problema

Un algoritmo para el problema de selección toma como entrada una colección de valores y un número . ${\displaystyle k}$ Produce el n-ésimo más pequeño de estos valores o, en algunas versiones del problema, una colección de los valores más pequeños. Para que esto esté bien definido, debería ser posible ordenar los valores en un orden del más pequeño al más grande; por ejemplo, pueden ser números enteros , números de punto flotante o algún otro tipo de objeto con una clave numérica. Sin embargo, no se supone que ya hayan sido ordenados. A menudo, los algoritmos de selección se limitan a un modelo de cálculo basado en la comparación , como en los algoritmos de ordenamiento por comparación , donde el algoritmo tiene acceso a una operación de comparación que puede determinar el orden relativo de dos valores cualesquiera, pero no puede realizar ningún otro tipo de operaciones aritméticas sobre estos valores. ^[1] ${\displaystyle k}$ ${\displaystyle k}$

Para simplificar el problema, algunos trabajos sobre este problema suponen que los valores son todos distintos entre sí , ^[2] o que se ha utilizado algún método de desempate consistente para asignar un orden a pares de elementos con el mismo valor entre sí. Otra variación en la definición del problema se refiere a la numeración de los valores ordenados: ¿el valor más pequeño se obtiene estableciendo , como ${\displaystyle k=0}$ en la numeración de matrices basada en cero , o se obtiene estableciendo , siguiendo ${\displaystyle k=1}$ las convenciones habituales del idioma inglés para el más pequeño, el segundo más pequeño, etc.? Este artículo sigue las convenciones utilizadas por Cormen et al., según las cuales todos los valores son distintos y el valor mínimo se obtiene de . ^[2] ${\displaystyle k=1}$

Con estas convenciones, el valor máximo, entre una colección de valores, se obtiene fijando . Cuando es un número impar , la mediana de la colección se obtiene fijando . Cuando es par, hay dos opciones para la mediana, que se obtienen redondeando esta opción de hacia abajo o hacia arriba, respectivamente: la mediana inferior con y la mediana superior con . ^[2] ${\displaystyle n}$ ${\displaystyle k=n}$ ${\displaystyle n}$ ${\displaystyle k=(n+1)/2}$ ${\displaystyle n}$ ${\displaystyle k}$ ${\displaystyle k=n/2}$ ${\displaystyle k=n/2+1}$

Algoritmos

Ordenamiento y selección de montón

Como algoritmo de base, la selección del valor más pequeño en una colección de valores se puede realizar mediante los dos pasos siguientes: ${\displaystyle k}$

• Ordenar la colección
• Si la salida del algoritmo de ordenamiento es una matriz , recupere su elemento número 1 ; de lo contrario, escanee la secuencia ordenada para encontrar el elemento número 1 . ${\displaystyle k}$ ${\displaystyle k}$

El tiempo de este método está dominado por el paso de ordenamiento, que requiere tiempo utilizando un ordenamiento por comparación . ^{[2] [3]} Incluso cuando se pueden utilizar algoritmos de ordenamiento de números enteros , estos son generalmente más lentos que el tiempo lineal que se puede lograr utilizando algoritmos de selección especializados. Sin embargo, la simplicidad de este enfoque lo hace atractivo, especialmente cuando se proporciona una rutina de ordenamiento altamente optimizada como parte de una biblioteca de tiempo de ejecución, pero no un algoritmo de selección. Para entradas de tamaño moderado, el ordenamiento puede ser más rápido que los algoritmos de selección no aleatorios, debido a los factores constantes más pequeños en su tiempo de ejecución. ^[4] Este método también produce una versión ordenada de la colección, que puede ser útil para otros cálculos posteriores, y en particular para la selección con otras opciones de . ^[3] ${\displaystyle \Theta (n\log n)}$ ${\displaystyle k}$

Para un algoritmo de ordenamiento que genera un elemento a la vez, como el ordenamiento por selección , el escaneo se puede realizar en tándem con el ordenamiento, y el ordenamiento se puede terminar una vez que se ha encontrado el elemento n . Un posible diseño de un grupo de consolación en un torneo de eliminación simple , en el que los equipos que perdieron ante el eventual ganador juegan otro mini-torneo para determinar el segundo lugar, puede verse como una instancia de este método. ^[5] La aplicación de esta optimización a heapsort produce el algoritmo heapselect , que puede seleccionar el valor n.º más pequeño en el tiempo . ^[6] Esto es rápido cuando es pequeño en relación con , pero degenera a para valores más grandes de , como la elección utilizada para encontrar la mediana. ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle O(n+k\log n)}$ ${\displaystyle k}$ ${\displaystyle n}$ ${\displaystyle O(n\log n)}$ ${\displaystyle k}$ ${\displaystyle k=n/2}$

Pivotando

Muchos métodos de selección se basan en elegir un elemento "pivote" especial de la entrada y usar comparaciones con este elemento para dividir los valores de entrada restantes en dos subconjuntos: el conjunto de elementos menores que el pivote y el conjunto de elementos mayores que el pivote. El algoritmo puede entonces determinar dónde se encuentra el valor más pequeño, basándose en una comparación de con los tamaños de estos conjuntos. En particular, si , el valor más pequeño está en , y se puede encontrar recursivamente aplicando el mismo algoritmo de selección a . Si , entonces el valor más pequeño es el pivote y se puede devolver inmediatamente. En el caso restante, el valor más pequeño está en , y más específicamente es el elemento en la posición de . Se puede encontrar aplicando un algoritmo de selección recursivamente, buscando el valor en esta posición en . ^[7] ${\displaystyle n-1}$ ${\displaystyle L}$ ${\displaystyle R}$ ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle k\leq |L|}$ ${\displaystyle k}$ ${\displaystyle L}$ ${\displaystyle L}$ ${\displaystyle k=|L|+1}$ ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle R}$ ${\displaystyle k-|L|-1}$ ${\displaystyle R}$ ${\displaystyle R}$

Al igual que con el algoritmo de ordenamiento rápido basado en pivoteo relacionado , la partición de la entrada en y puede realizarse creando nuevas colecciones para estos conjuntos, o mediante un método que particione un tipo de datos de lista o matriz determinado en el lugar. Los detalles varían según cómo se represente la colección de entrada. ^[8] El tiempo para comparar el pivote con todos los demás valores es . ^[7] Sin embargo, los métodos de pivoteo difieren en cómo eligen el pivote, lo que afecta el tamaño de los subproblemas en cada llamada recursiva. La eficiencia de estos métodos depende en gran medida de la elección del pivote. Si el pivote se elige mal, el tiempo de ejecución de este método puede ser tan lento como . ^[4] ${\displaystyle L}$ ${\displaystyle R}$ ${\displaystyle O(n)}$ ${\displaystyle O(n^{2})}$

• Si el pivote estuviera exactamente en la mediana de la entrada, entonces cada llamada recursiva tendría como máximo la mitad de valores que la llamada anterior, y los tiempos totales sumarían en una serie geométrica hasta . ${\displaystyle O(n)}$ Sin embargo, encontrar la mediana es en sí mismo un problema de selección, en toda la entrada original. Intentar encontrarla mediante una llamada recursiva a un algoritmo de selección conduciría a una recursión infinita, porque el tamaño del problema no disminuiría en cada llamada. ^[7]
• Quickselect elige el pivote de manera uniforme y aleatoria a partir de los valores de entrada. Puede describirse como un algoritmo de poda y búsqueda , ^[9] una variante de quicksort , con la misma estrategia de pivote, pero donde quicksort realiza dos llamadas recursivas para ordenar las dos subcolecciones y , quickselect solo realiza una de estas dos llamadas. Su tiempo esperado es . ^{[2] [7] [9]} Para cualquier constante , la probabilidad de que su número de comparaciones exceda es superexponencialmente pequeña en . ^[10] ${\displaystyle L}$ ${\displaystyle R}$ ${\displaystyle O(n)}$ ${\displaystyle C}$ ${\displaystyle Cn}$ ${\displaystyle C}$
• El algoritmo Floyd-Rivest , una variación de selección rápida, elige un pivote muestreando aleatoriamente un subconjunto de valores de datos, para un tamaño de muestra determinado , y luego seleccionando recursivamente dos elementos algo por encima y por debajo de la posición de la muestra para usarlos como pivotes. Con esta elección, es probable que quede intercalado entre los dos pivotes, de modo que después de pivotar solo quede una pequeña cantidad de valores de datos entre los pivotes para una llamada recursiva. Este método puede lograr un número esperado de comparaciones que es . ^[11] En su trabajo original, Floyd y Rivest afirmaron que el término podría hacerse tan pequeño como mediante un esquema de muestreo recursivo, pero se ha cuestionado la exactitud de su análisis. ^{[12] [13]} En cambio, un análisis más riguroso ha demostrado que una versión de su algoritmo logra para este término. ^[14] Aunque el análisis habitual tanto del algoritmo de selección rápida como del algoritmo Floyd-Rivest supone el uso de un generador de números aleatorios verdaderos , se ha demostrado que una versión del algoritmo Floyd-Rivest que utiliza un generador de números pseudoaleatorios alimentado solo con una cantidad logarítmica de bits aleatorios verdaderos se ejecuta en tiempo lineal con alta probabilidad. ^[15] ${\displaystyle r}$ ${\displaystyle r}$ ${\displaystyle rk/n}$ ${\displaystyle k}$ ${\displaystyle n+\min(k,n-k)+o(n)}$ ${\displaystyle o(n)}$ ${\displaystyle O({\sqrt {n}})}$ ${\displaystyle O({\sqrt {n\log n}})}$

Visualización de la selección de pivotes para el método de la mediana de medianas . Cada conjunto de cinco elementos se muestra como una columna de puntos en la figura, ordenados en orden creciente de arriba a abajo. Si sus medianas (los puntos verdes y morados en la fila del medio) se ordenan en orden creciente de izquierda a derecha, y la mediana de medianas se elige como pivote, entonces los elementos en el cuadrante superior izquierdo serán menores que el pivote, y los elementos en el cuadrante inferior derecho serán mayores que el pivote, lo que muestra que muchos elementos se eliminarán mediante el pivote. ${\displaystyle 3n/10}$ ${\displaystyle 3n/10}$

• El método de la mediana de medianas divide la entrada en conjuntos de cinco elementos y utiliza algún otro método no recursivo para encontrar la mediana de cada uno de estos conjuntos en tiempo constante por conjunto. Luego, recursivamente se llama a sí mismo para encontrar la mediana de estas medianas. El uso de la mediana de medianas resultante como pivote produce una partición con . Por lo tanto, un problema sobre elementos se reduce a dos problemas recursivos sobre elementos (para encontrar el pivote) y como máximo elementos (después de que se utiliza el pivote). El tamaño total de estos dos subproblemas recursivos es como máximo , lo que permite analizar el tiempo total como una serie geométrica que suma . A diferencia de quickselect, este algoritmo es determinista, no aleatorio. ^{[2] [4] [5]} Fue el primer algoritmo de selección determinista de tiempo lineal conocido, ^[5] y se enseña comúnmente en clases de algoritmos de pregrado como un ejemplo de divide y vencerás que no se divide en dos subproblemas iguales. ^{[2] [4] [9] [16]} Sin embargo, los altos factores constantes en su límite de tiempo lo hacen más lento que la selección rápida en la práctica, ^{[3] [9]} y más lento incluso que la clasificación para entradas de tamaño moderado. ^[4] ${\displaystyle n/5}$ ${\displaystyle \max(|L|,|R|)\leq 7n/10}$ ${\displaystyle n}$ ${\displaystyle n/5}$ ${\displaystyle 7n/10}$ ${\displaystyle 9n/10}$ ${\displaystyle O(n)}$ ${\displaystyle O(n)}$
• Se pueden utilizar algoritmos híbridos como introselect para lograr el rendimiento práctico de quickselect con un recurso a las medianas de las medianas que garantizan el peor tiempo posible. ^[17] ${\displaystyle O(n)}$

Fábricas

Los algoritmos de selección determinista con los números más pequeños conocidos de comparaciones, para valores de que están lejos de o , se basan en el concepto de fábricas , introducido en 1976 por Arnold Schönhage , Mike Paterson y Nick Pippenger . ^[18] Estos son métodos que construyen órdenes parciales de ciertos tipos especificados, en pequeños subconjuntos de valores de entrada, utilizando comparaciones para combinar órdenes parciales más pequeñas. Como un ejemplo muy simple, un tipo de fábrica puede tomar como entrada una secuencia de órdenes parciales de un solo elemento, comparar pares de elementos de estas órdenes y producir como salida una secuencia de conjuntos totalmente ordenados de dos elementos. Los elementos utilizados como entradas para esta fábrica podrían ser valores de entrada que aún no se han comparado con nada, o valores "de desecho" producidos por otras fábricas. El objetivo de un algoritmo basado en fábricas es combinar diferentes fábricas, con las salidas de algunas fábricas yendo a las entradas de otras, para finalmente obtener una orden parcial en la que un elemento (el º más pequeño) es más grande que algunos otros elementos y más pequeño que otros. Un diseño cuidadoso de estas fábricas conduce a un algoritmo que, cuando se aplica para hallar la mediana, utiliza como máximo comparaciones. Para otros valores de , el número de comparaciones es menor. ^[19] ${\displaystyle k}$ ${\displaystyle 1}$ ${\displaystyle n}$ ${\displaystyle k}$ ${\displaystyle k-1}$ ${\displaystyle n-k}$ ${\displaystyle 2.942n}$ ${\displaystyle k}$

Algoritmos paralelos

Los algoritmos paralelos para la selección se han estudiado desde 1975, cuando Leslie Valiant introdujo el modelo de árbol de comparación paralela para analizar estos algoritmos, y demostró que en este modelo la selección usando un número lineal de comparaciones requiere pasos paralelos, incluso para seleccionar el mínimo o el máximo. ^[20] Los investigadores encontraron posteriormente algoritmos paralelos para la selección en pasos, que coinciden con este límite. ^{[21] [22]} En un modelo de árbol de comparación paralela aleatorio es posible realizar la selección en un número acotado de pasos y un número lineal de comparaciones. ^[23] En el modelo de computación RAM paralela más realista , con acceso exclusivo a memoria de lectura y escritura exclusiva, la selección se puede realizar a tiempo con los procesadores, lo que es óptimo tanto en tiempo como en número de procesadores. ^[24] Con acceso a memoria concurrente, en general es posible un tiempo paralelo ligeramente más rápido , ^[25] y el término en el límite de tiempo se puede reemplazar por . ^[26] ${\displaystyle \Omega (\log \log n)}$ ${\displaystyle O(\log \log n)}$ ${\displaystyle O(\log n)}$ ${\displaystyle O(n/\log n)}$ ${\displaystyle \log n}$ ${\displaystyle \log k}$

Estructuras de datos sublineales

Cuando los datos ya están organizados en una estructura de datos , puede ser posible realizar la selección en una cantidad de tiempo que es sublineal en el número de valores. Como un caso simple de esto, para los datos ya ordenados en una matriz, la selección del elemento n puede realizarse mediante una única búsqueda en la matriz, en tiempo constante. ^[27] Para los valores organizados en una matriz bidimensional de tamaño , con filas y columnas ordenadas, la selección puede realizarse en tiempo , o más rápido cuando es pequeño en relación con las dimensiones de la matriz. ^{[27] [28]} Para una colección de matrices unidimensionales ordenadas, con elementos menores que el elemento seleccionado en la matriz n , el tiempo es . ^[28] ${\displaystyle k}$ ${\displaystyle m\times n}$ ${\displaystyle O{\bigl (}m\log(2n/m){\bigr )}}$ ${\displaystyle k}$ ${\displaystyle m}$ ${\displaystyle k_{i}}$ ${\displaystyle i}$ ${\textstyle O{\bigl (}m+\sum _{i=1}^{m}\log(k_{i}+1){\bigr )}}$

La selección de datos en un montón binario lleva tiempo . ${\displaystyle O(k)}$ Esto es independiente del tamaño del montón y más rápido que el límite de tiempo que se obtendría de la búsqueda de mejor primero . ^{[28] [29]} Este mismo método se puede aplicar de forma más general a los datos organizados como cualquier tipo de árbol ordenado por montón (un árbol en el que cada nodo almacena un valor en el que el padre de cada nodo no raíz tiene un valor menor que su hijo). Este método de realizar la selección en un montón se ha aplicado a problemas de lista de múltiples soluciones a problemas de optimización combinatoria, como encontrar los k caminos más cortos en un gráfico ponderado, definiendo un espacio de estado de soluciones en forma de un árbol ordenado por montón definido implícitamente y luego aplicando este algoritmo de selección a este árbol. ^[30] En la otra dirección, los algoritmos de selección de tiempo lineal se han utilizado como una subrutina en una estructura de datos de cola de prioridad relacionada con el montón, mejorando el tiempo para extraer su elemento n de a ; aquí está el logaritmo iterado . ^[31] ${\displaystyle n}$ ${\displaystyle O(k\log n)}$ ${\displaystyle k}$ ${\displaystyle O(\log n)}$ ${\displaystyle O(\log ^{*}n+\log k)}$ ${\displaystyle \log ^{*}n}$

Para una colección de valores de datos que experimentan inserciones y eliminaciones dinámicas, el árbol estadístico de orden aumenta una estructura de árbol de búsqueda binaria autoequilibrada con una cantidad constante de información adicional por nodo de árbol, lo que permite que las inserciones, eliminaciones y consultas de selección que solicitan el elemento n.º en el conjunto actual se realicen todas en el tiempo por operación. ^[2] Yendo más allá del modelo de comparación de cálculo, son posibles tiempos más rápidos por operación para valores que son enteros pequeños, en los que se permiten operaciones aritméticas binarias. ^[32] No es posible para un algoritmo de transmisión con memoria sublineal tanto en como resuelva consultas de selección de manera exacta para datos dinámicos, pero el boceto count–min se puede utilizar para resolver consultas de selección de manera aproximada, al encontrar un valor cuya posición en el ordenamiento de los elementos (si se agregara a ellos) estaría dentro de los pasos de , para un boceto cuyo tamaño está dentro de factores logarítmicos de . ^[33] ${\displaystyle k}$ ${\displaystyle O(\log n)}$ ${\displaystyle n}$ ${\displaystyle k}$ ${\displaystyle \varepsilon n}$ ${\displaystyle k}$ ${\displaystyle 1/\varepsilon }$

Límites inferiores

El tiempo de ejecución de los algoritmos de selección descritos anteriormente es necesario, porque un algoritmo de selección que puede manejar entradas en un orden arbitrario debe tomarse ese tiempo para examinar todas sus entradas. Si alguno de sus valores de entrada no se compara, ese valor podría ser el que debería haberse seleccionado, y el algoritmo puede llegar a producir una respuesta incorrecta. ^[28] Más allá de este simple argumento, ha habido una cantidad significativa de investigación sobre el número exacto de comparaciones necesarias para la selección, tanto en los casos aleatorios como deterministas. ${\displaystyle O(n)}$

La selección del mínimo de valores requiere comparaciones, porque los valores que no se seleccionan deben haber sido determinados como no mínimos, al ser los mayores en alguna comparación, y no puede haber dos de estos valores mayores en la misma comparación. El mismo argumento se aplica simétricamente a la selección del máximo. ^[14] ${\displaystyle n}$ ${\displaystyle n-1}$ ${\displaystyle n-1}$

El siguiente caso más simple es seleccionar el segundo más pequeño. Después de varios intentos incorrectos, el primer límite inferior estricto en este caso fue publicado en 1964 por el matemático soviético Sergey Kislitsyn . Se puede demostrar observando que seleccionar el segundo más pequeño también requiere distinguir el valor más pequeño del resto, y considerando el número de comparaciones que involucran el valor más pequeño que hace un algoritmo para este problema. Cada uno de los elementos que se compararon con el valor más pequeño es un candidato para el segundo más pequeño, y de estos valores se debe encontrar un valor mayor que otro valor en una segunda comparación para descartarlos como el segundo más pequeño. Con valores siendo el mayor en al menos una comparación, y valores siendo el mayor en al menos dos comparaciones, hay un total de al menos comparaciones. Un argumento adversario , en el que el resultado de cada comparación se elige para maximizar (sujeto a la consistencia con al menos un ordenamiento posible) en lugar de por los valores numéricos de los elementos dados, muestra que es posible forzar a que sea al menos . Por lo tanto, el número de comparaciones en el peor de los casos necesarias para seleccionar el segundo más pequeño es , el mismo número que se obtendría al realizar un torneo de eliminación simple con un torneo de desempate entre los valores que perdieron contra el valor más pequeño. Sin embargo, el número esperado de comparaciones de un algoritmo de selección aleatoria puede ser mejor que este límite; por ejemplo, seleccionar el segundo más pequeño de seis elementos requiere siete comparaciones en el peor de los casos, pero puede hacerse mediante un algoritmo aleatorio con un número esperado de 6,5 comparaciones. ^[14] ${\displaystyle p}$ ${\displaystyle p}$ ${\displaystyle p-1}$ ${\displaystyle n-1}$ ${\displaystyle p-1}$ ${\displaystyle n+p-2}$ ${\displaystyle p}$ ${\displaystyle p}$ ${\displaystyle \log _{2}n}$ ${\displaystyle n+\lceil \log _{2}n\rceil -2}$

En términos más generales, seleccionar el elemento n de entre requiere al menos comparaciones que, en el caso promedio, coincidan con el número de comparaciones del algoritmo Floyd-Rivest hasta su término. El argumento se hace directamente para algoritmos deterministas, con un número de comparaciones que se promedia sobre todas las permutaciones posibles de los valores de entrada. ^[1] Por el principio de Yao , también se aplica al número esperado de comparaciones para un algoritmo aleatorio en su entrada del peor caso. ^[34] ${\displaystyle k}$ ${\displaystyle n}$ ${\displaystyle n+\min(k,n-k)-O(1)}$ ${\displaystyle o(n)}$

Para los algoritmos deterministas, se ha demostrado que seleccionar el elemento n requiere comparaciones, donde es la función de entropía binaria . ^[35] El caso especial de búsqueda de la mediana tiene un límite inferior ligeramente mayor en el número de comparaciones, al menos , para . ^[36] ${\displaystyle k}$ ${\displaystyle {\bigl (}1+H(k/n){\bigr )}n+\Omega ({\sqrt {n}})}$ $${\displaystyle H(x)=x\log _{2}{\frac {1}{x}}+(1-x)\log _{2}{\frac {1}{1-x}}}$$ ${\displaystyle (2+\varepsilon )n}$ ${\displaystyle \varepsilon \approx 2^{-80}}$

Números exactos de comparaciones

Hallar la mediana de cinco valores mediante seis comparaciones. Cada paso muestra las comparaciones que se realizarán a continuación como segmentos de línea amarillos y un diagrama de Hasse de las relaciones de orden encontradas hasta ahora (con menor=menor y mayor=mayor) como segmentos de línea azules. Ya se ha descubierto que los elementos rojos son mayores que otros tres y, por lo tanto, no pueden ser la mediana. El mayor de los dos elementos en la comparación final es la mediana.

Knuth proporciona el siguiente triángulo de números que resumen pares de y para los cuales se conoce el número exacto de comparaciones necesarias para un algoritmo de selección óptimo. La fila n.° del triángulo (que comienza con en la fila superior) proporciona el número de comparaciones para entradas de valores, y el número n .° dentro de cada fila proporciona el número de comparaciones necesarias para seleccionar el valor n.° más pequeño de una entrada de ese tamaño. Las filas son simétricas porque seleccionar el valor n.° más pequeño requiere exactamente el mismo número de comparaciones, en el peor de los casos, que seleccionar el valor n. ° más grande. ^[14] ${\displaystyle n}$ ${\displaystyle k}$ ${\displaystyle n}$ ${\displaystyle n=1}$ ${\displaystyle n}$ ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle k}$

0

1 1

2 3 2

3 4 4 3

4 6 6 6 4

5 7 8 8 7 5

6 8 10 10 10 8 6

7 9 11 12 12 11 9 7

8 11 12 14 14 14 12 11 8

9 12 14 15 16 16 15 14 12 9

La mayoría, pero no todas, de las entradas en la mitad izquierda de cada fila se pueden encontrar usando la fórmula Esto describe el número de comparaciones realizadas por un método de Abdollah Hadian y Milton Sobel , relacionado con heapselect, que encuentra el valor más pequeño usando un torneo de eliminación simple y luego usa repetidamente un torneo más pequeño entre los valores eliminados por los eventuales ganadores del torneo para encontrar los siguientes valores sucesivos hasta llegar al más pequeño. ^{[14] [37]} Se demostró que algunas de las entradas más grandes eran óptimas usando una búsqueda por computadora. ^{[14] [38]} $${\displaystyle n-k+(k-1){\bigl \lceil }\log _{2}(n+2-k){\bigr \rceil }.}$$ ${\displaystyle k}$

Soporte de idiomas

Muy pocos lenguajes tienen soporte integrado para la selección general, aunque muchos proporcionan funciones para encontrar el elemento más pequeño o más grande de una lista. Una excepción notable es la Biblioteca de plantillas estándar para C++ , que proporciona un nth_elementmétodo basado en plantillas con una garantía de tiempo lineal esperado. ^[3]

La biblioteca estándar de Pythonheapq.nsmallest incluye funciones heapq.nlargestpara devolver los elementos más pequeños o más grandes de una colección, en orden ordenado. La implementación mantiene un montón binario , limitado a contener elementos e inicializado con los primeros elementos de la colección. Luego, cada elemento posterior de la colección puede reemplazar el elemento más grande o más pequeño en el montón si es más pequeño o más grande que este elemento. El uso de memoria del algoritmo es superior a heapselect (el primero solo mantiene elementos en la memoria a la vez, mientras que el segundo requiere manipular todo el conjunto de datos en la memoria). El tiempo de ejecución depende del orden de los datos. El mejor caso es para datos ya ordenados. El peor caso es para datos ordenados de forma inversa. En los casos promedio, es probable que haya pocas actualizaciones del montón y la mayoría de los elementos de entrada se procesan con una sola comparación. Por ejemplo, extraer los 100 valores más grandes o más pequeños de 10 000 000 de entradas aleatorias hace 10 009 401 comparaciones en promedio. ^[39] ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle O((n-k)+k\log k)}$ ${\displaystyle O(n\log k)}$

Desde 2017, Matlab incluye funciones maxk()y mink()que devuelven los valores máximos (mínimos) de un vector, así como sus índices. La documentación de Matlab no especifica qué algoritmo utilizan estas funciones ni cuál es su tiempo de ejecución. ^[40] ${\displaystyle k}$

Historia

Quickselect fue presentado sin análisis por Tony Hoare en 1965, ^[41] y analizado por primera vez en un informe técnico de 1971 por Donald Knuth . ^[11] El primer algoritmo de selección determinista en el tiempo lineal conocido es el método de la mediana de medianas , publicado en 1973 por Manuel Blum , Robert W. Floyd , Vaughan Pratt , Ron Rivest y Robert Tarjan . ^[5] Rastrean la formulación del problema de selección al trabajo de Charles L. Dodgson (mejor conocido como Lewis Carroll ), quien en 1883 señaló que el diseño habitual de los torneos deportivos de eliminación simple no garantiza que el segundo mejor jugador gane el segundo lugar, ^{[5] [42]} y al trabajo de Hugo Steinhaus alrededor de 1930, quien siguió esta misma línea de pensamiento al pedir un diseño de torneo que pueda hacer esta garantía, con un número mínimo de juegos jugados (es decir, comparaciones). ^[5]

Véase también

• Mediana geométrica § Cálculo , algoritmos para generalizaciones de medianas en dimensiones superiores
• Filtro de mediana , aplicación de algoritmos de búsqueda de mediana en el procesamiento de imágenes

Referencias

1. Cunto, Walter; Munro, J. Ian (1989). "Selección de casos promedio". Revista de la ACM . 36 (2): 270–279. doi : 10.1145/62044.62047 . MR  1072421. S2CID  10947879.
2. Cormen, Thomas H. ; Leiserson, Charles E. ; Rivest, Ronald L. ; Stein, Clifford (2009) [1990]. "Capítulo 9: Medianas y estadísticas de orden". Introducción a los algoritmos (3.ª ed.). MIT Press y McGraw-Hill. págs. 213–227. ISBN 0-262-03384-4.; "Sección 14.1: Estadísticas de pedidos dinámicos", págs. 339–345
3. Skiena, Steven S. (2020). "17.3: Mediana y selección". Manual de diseño de algoritmos . Textos en informática (tercera edición). Springer. págs. 514–516. doi :10.1007/978-3-030-54256-6. ISBN 978-3-030-54255-9. Sr.  4241430. S2CID  22382667.
4. Erickson, Jeff (junio de 2019). "1.8: Selección en tiempo lineal". Algoritmos. págs. 35–39.
5. Blum, Manuel ; Floyd, Robert W. ; Pratt, Vaughan ; Rivest, Ronald L. ; Tarjan, Robert E. (1973). "Límites de tiempo para la selección" (PDF) . Revista de Ciencias de la Computación y de Sistemas . 7 (4): 448–461. doi : 10.1016/S0022-0000(73)80033-9 . MR  0329916.
6. Brodal, Gerth Stølting (2013). "Una encuesta sobre colas de prioridad". En Brodnik, Andrej; López-Ortiz, Alejandro; Raman, Venkatesh; Viola, Alfredo (eds.). Estructuras de datos, flujos y algoritmos eficientes en el uso del espacio: artículos en honor a J. Ian Munro con motivo de su 66.º cumpleaños . Lecture Notes in Computer Science. Vol. 8066. Springer. págs. 150–163. doi :10.1007/978-3-642-40273-9_11. ISBN . 978-3-642-40272-2.
7. Kleinberg, Jon ; Tardos, Éva (2006). "13.5 Divide y vencerás aleatorizado: búsqueda de la mediana y ordenación rápida". Algorithm Design . Addison-Wesley. págs. 727–734. ISBN 9780321295354.
8. Por ejemplo, Cormen et al. utilizan una partición de matriz en el lugar, mientras que Kleinberg y Tardos describen la entrada como un conjunto y utilizan un método que la divide en dos nuevos conjuntos.
9. Goodrich, Michael T. ; Tamassia, Roberto (2015). "9.2: Selección". Diseño de algoritmos y aplicaciones . Wiley. págs. 270–275. ISBN 978-1-118-33591-8.
10. Devroye, Luc (1984). "Límites exponenciales para el tiempo de ejecución de un algoritmo de selección" (PDF) . Revista de Ciencias de la Computación y de Sistemas . 29 (1): 1–7. doi :10.1016/0022-0000(84)90009-6. MR  0761047. Devroye, Luc (2001). "Sobre el peor momento probabilístico de 'find'" (PDF) . Algorithmica . 31 (3): 291–303. doi :10.1007/s00453-001-0046-2. MR  1855252. S2CID  674040.
11. Floyd, Robert W. ; Rivest, Ronald L. (marzo de 1975). "Límites temporales esperados para la selección". Comunicaciones de la ACM . 18 (3): 165–172. doi : 10.1145/360680.360691 . S2CID  3064709.Véase también "Algoritmo 489: el algoritmo SELECT para encontrar el elemento más pequeño ", pág. 173, doi :10.1145/360680.360694. ${\displaystyle i}$ ${\displaystyle n}$
12. Brown, Theodore (septiembre de 1976). "Observación sobre el algoritmo 489". ACM Transactions on Mathematical Software . 2 (3): 301–304. doi :10.1145/355694.355704. S2CID  13985011.
13. Postmus, JT; Rinnooy Kan, AHG ; Timmer, GT (1983). "Un método de selección dinámica eficiente". Comunicaciones de la ACM . 26 (11): 878–881. doi : 10.1145/182.358440 . MR  0784120. S2CID  3211474.
14. Knuth, Donald E. (1998). "Sección 5.3.3: Selección por comparación mínima". El arte de la programación informática, volumen 3: Ordenación y búsqueda (2.ª ed.). Addison-Wesley. págs. 207–219. ISBN 0-201-89685-0.
15. Karloff, Howard J.; Raghavan, Prabhakar (1993). "Algoritmos aleatorios y números pseudoaleatorios". Revista de la ACM . 40 (3): 454–476. doi : 10.1145/174130.174132 . MR  1370358. S2CID  17956460.
16. Gurwitz, Chaya (1992). "Sobre la enseñanza de algoritmos de búsqueda de medianas". IEEE Transactions on Education . 35 (3): 230–232. Bibcode :1992ITEdu..35..230G. doi :10.1109/13.144650.
17. Musser, David R. (agosto de 1997). "Algoritmos de selección y ordenación introspectivos". Software: práctica y experiencia . 27 (8). Wiley: 983–993. doi :10.1002/(sici)1097-024x(199708)27:8<983::aid-spe117>3.0.co;2-#.
18. Schönhage, A. ; Paterson, M. ; Pippenger, N. (1976). "Encontrar la mediana". Revista de Ciencias de la Computación y de Sistemas . 13 (2): 184–199. doi :10.1016/S0022-0000(76)80029-3. MR  0428794. S2CID  29867292.
19. Dor, Dorit ; Zwick, Uri (1999). "Selección de la mediana". Revista SIAM de Informática . 28 (5): 1722–1758. doi :10.1137/S0097539795288611. MR  1694164. S2CID  2633282.
20. Valiant, Leslie G. (1975). "Paralelismo en problemas de comparación". Revista SIAM de Computación . 4 (3): 348–355. doi :10.1137/0204030. MR  0378467.
21. Ajtai, Miklós ; Komlós, János ; Steiger, WL; Szemerédi, Endre (1989). "La selección paralela óptima tiene complejidad ". Revista de Ciencias de la Computación y de Sistemas . 38 (1): 125-133. doi :10.1016/0022-0000(89)90035-4. SEÑOR  0990052. ${\displaystyle O(\log \log n)}$
22. Azar, Yossi; Pippenger, Nicholas (1990). "Selección paralela". Matemáticas Aplicadas Discretas . 27 (1–2): 49–58. doi :10.1016/0166-218X(90)90128-Y. MR  1055590.
23. Reischuk, Rüdiger (1985). "Algoritmos probabilísticos paralelos para ordenamiento y selección". Revista SIAM de Computación . 14 (2): 396–409. doi :10.1137/0214030. MR  0784745.
24. Han, Yijie (2007). "Selección paralela óptima". ACM Transactions on Algorithms . 3 (4): A38:1–A38:11. doi :10.1145/1290672.1290675. MR  2364962. S2CID  9645870.
25. Chaudhuri, Shiva; Hagerup, Torben; Raman, Rajeev (1993). "Selección paralela determinista aproximada y exacta". En Borzyszkowski, Andrzej M.; Sokolowski, Stefan (eds.). Fundamentos matemáticos de la informática 1993, 18.º simposio internacional, MFCS'93, Gdansk, Polonia, 30 de agosto – 3 de septiembre de 1993, Actas . Apuntes de clase en informática. Vol. 711. Springer. págs. 352–361. doi :10.1007/3-540-57182-5_27. hdl : 11858/00-001M-0000-0014-B748-C . ISBN . 978-3-540-57182-7.
26. Dietz, Paul F.; Raman, Rajeev (1999). "Selección de rangos pequeños en paralelo, con aplicaciones a la construcción de montículos". Journal of Algorithms . 30 (1): 33–51. doi :10.1006/jagm.1998.0971. MR  1661179.
27. Frederickson, Greg N.; Johnson, Donald B. (1984). "Selección generalizada y clasificación: matrices ordenadas". Revista SIAM de Computación . 13 (1): 14–30. doi :10.1137/0213002. MR  0731024.
28. Kaplan, Haim; Kozma, László; Zamir, Or; Zwick, Uri (2019). "Selección de montículos, matrices ordenadas por filas y uso de montículos suaves". En Fineman, Jeremy T.; Mitzenmacher, Michael (eds.). 2.º Simposio sobre simplicidad en algoritmos, SOSA 2019, 8 y 9 de enero de 2019, San Diego, CA, EE. UU . . OASIcs. Vol. 69. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. págs. 5:1–5:21. arXiv : 1802.07041 . doi : 10.4230/OASIcs.SOSA.2019.5 . ${\displaystyle X+Y}$
29. Frederickson, Greg N. (1993). "Un algoritmo óptimo para la selección en un min-heap". Información y computación . 104 (2): 197–214. doi : 10.1006/inco.1993.1030 . MR  1221889.
30. Eppstein, David (1999). "Encontrar los caminos más cortos". Revista SIAM de Computación . 28 (2): 652–673. doi :10.1137/S0097539795290477. MR  1634364. ${\displaystyle k}$
31. Babenko, Maxim; Kolesnichenko, Ignat; Smirnov, Ivan (2019). "Montón en cascada: hacia extracciones óptimas en el tiempo". Teoría de sistemas informáticos . 63 (4): 637–646. doi :10.1007/s00224-018-9866-1. MR  3942251. S2CID  253740380.
32. Pătraşcu, Mihai ; Thorup, Mikkel (2014). "Conjuntos de números enteros dinámicos con rango óptimo, selección y búsqueda de predecesores". 55.º Simposio anual del IEEE sobre fundamentos de la informática, FOCS 2014, Filadelfia, Pensilvania, EE. UU., 18-21 de octubre de 2014 . IEEE Computer Society. págs. 166-175. arXiv : 1408.3045 . doi :10.1109/FOCS.2014.26. ISBN 978-1-4799-6517-5.
33. Cormode, Graham; Muthukrishnan, S. (2005). "Un resumen mejorado del flujo de datos: el esquema count-min y sus aplicaciones". Journal of Algorithms . 55 (1): 58–75. doi :10.1016/j.jalgor.2003.12.001. MR  2132028.
34. Chan, Timothy M. (2010). "Límites inferiores espacio-temporales basados ​​en comparación para la selección". ACM Transactions on Algorithms . 6 (2): A26:1–A26:16. doi :10.1145/1721837.1721842. MR  2675693. S2CID  11742607.
35. Bent, Samuel W.; John, John W. (1985). "Encontrar la mediana requiere comparaciones". En Sedgewick, Robert (ed.). Actas del 17.º Simposio anual de la ACM sobre teoría de la computación, 6-8 de mayo de 1985, Providence, Rhode Island, EE. UU . . Association for Computing Machinery. págs. 213-216. doi : 10.1145/22145.22169 . ISBN ${\displaystyle 2n}$ 0-89791-151-2.
36. Dor, Dorit ; Zwick, Uri (2001). "La selección de la mediana requiere comparaciones". Revista SIAM de Matemáticas Discretas . 14 (3): 312–325. doi :10.1137/S0895480199353895. MR  1857348. ${\displaystyle (2+\varepsilon )N}$
37. Hadian, Abdollah; Sobel, Milton (mayo de 1969). Selección del -ésimo mayor número mediante comparaciones binarias sin error (informe). School of Statistics Technical Reports. Vol. 121. Universidad de Minnesota. hdl :11299/199105. ${\displaystyle t}$
38. Gasarch, William ; Kelly, Wayne; Pugh, William (julio de 1996). "Encontrar el mayor número de para los pequeños ". ACM SIGACT News . 27 (2): 88–96. doi :10.1145/235767.235772. S2CID  3133332. ${\displaystyle i}$ ${\displaystyle n}$ ${\displaystyle i,n}$
39. "Código fuente del paquete heapq". Biblioteca Python . Consultado el 6 de agosto de 2023 .; consulte también la comparación vinculada del rendimiento del algoritmo en los datos del mejor caso.
40. "mink: Encuentra los k elementos más pequeños de una matriz". Documentación de Matlab R2023a . Mathworks . Consultado el 30 de marzo de 2023 .
41. Hoare, CAR (julio de 1961). "Algoritmo 65: Encontrar". Comunicaciones de la ACM . 4 (7): 321–322. doi :10.1145/366622.366647.
42. Dodgson, Charles L. (1883). Torneos de tenis sobre césped: el verdadero método de asignación de premios con una prueba de la falacia del método actual . Londres: Macmillan and Co.Véase también Wilson, Robin; Moktefi, Amirouche, eds. (2019). "Torneos de tenis sobre césped". El mundo matemático de Charles L. Dodgson (Lewis Carroll) . Oxford University Press. pág. 129. ISBN. 9780192549013.