Hispanopedia Wiki
Articulo de referencia

Algoritmo de selección

En ciencias de la computación , un algoritmo de selección es un algoritmo para encontrar el k {\displaystyle k} el valor más pequeño en una colección de valores ordenables, como...

Hispanopedia WikiContenido en espanolLectura gratuita
Este es un buen artículo. Haz clic aquí para obtener más información.

En ciencias de la computación , un algoritmo de selección es un algoritmo para encontrar elk{\displaystyle k}el valor más pequeño en una colección de valores ordenables, como números. El valor que encuentra se llamak{\displaystyle k}estadística de orden n . La selección incluye como casos especiales los problemas de encontrar el elemento mínimo , la mediana y el máximo en la colección. Los algoritmos de selección incluyen quickselect y el algoritmo de la mediana de medianas . Cuando se aplica a una colección denorte{\displaystyle n}valores, estos algoritmos toman tiempo lineal ,O(norte){\displaystyle O(n)}como se expresa utilizando la notación Big O. Para datos que ya están estructurados, es posible que existan algoritmos más rápidos; como caso extremo, la selección en un arreglo ya ordenado lleva tiempo.O(1){\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úmerok{\displaystyle k}. Genera elk{\displaystyle k}el menor de estos valores, o, en algunas versiones del problema, una colección de losk{\displaystyle k}valores más pequeños. Para que esto esté bien definido, debería ser posible ordenar los valores de menor a mayor; por ejemplo, pueden ser enteros , números de coma flotante o algún otro tipo de objeto con una clave numérica. Sin embargo, no se asume que ya estén ordenados. A menudo, los algoritmos de selección se limitan a un modelo de computación basado en comparaciones , como en los algoritmos de ordenación 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 ]

Para simplificar el problema, algunos trabajos sobre este tema asumen 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. Otra variación en la definición del problema se refiere a la numeración de los valores ordenados: es el valor más pequeño obtenido al establecerk=0{\displaystyle k=0}, como en la numeración de matrices basada en cero , o se obtiene estableciendok=1{\displaystyle k=1}¿ Siguiendo 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 dek=1{\displaystyle k=1}. [ 2 ]

Con estas convenciones, el valor máximo, entre una colección denorte{\displaystyle n}valores, se obtiene al configurark=norte{\displaystyle k=n}. Cuandonorte{\displaystyle n}es un número impar , la mediana de la colección se obtiene estableciendok=(norte+1)/2{\displaystyle k=(n+1)/2}. Cuandonorte{\displaystyle n}es par, hay dos opciones para la mediana, obtenidas redondeando esta elección dek{\displaystyle k}hacia abajo o hacia arriba, respectivamente: la mediana inferior conk=norte/2{\displaystyle k=n/2}y la mediana superior conk=norte/2+1{\displaystyle k=n/2+1}. [ 2 ]

Algoritmos

Ordenación y selección de montículos

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

  • Ordenar la colección
  • Si la salida del algoritmo de ordenación es una matriz , recupere suk{\displaystyle k}el enésimo elemento; de lo contrario, recorra la secuencia ordenada para encontrar elk{\displaystyle k}elemento th .

El tiempo para este método está dominado por el paso de clasificación, que requiereΘ(norteregistro⁡norte){\displaystyle \Theta (n\log n)}tiempo usando una ordenación por comparación . [ 2 ] [ 3 ] Incluso cuando se pueden usar algoritmos de ordenación de enteros , estos son generalmente más lentos que el tiempo lineal que se puede lograr usando algoritmos de selección especializados. Sin embargo, la simplicidad de este enfoque lo hace atractivo, especialmente cuando se proporciona una rutina de ordenación 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, la ordenación puede ser más rápida 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 dek{\displaystyle k}. [ 3 ]

Para un algoritmo de ordenación que genera un elemento a la vez, como la ordenación por selección , el escaneo se puede realizar en tándem con la ordenación, y la ordenación se puede terminar una vez quek{\displaystyle k}Se ha encontrado el elemento n. Un posible diseño de un cuadro de consolación en un torneo de eliminación simple , en el que los equipos que perdieron contra el eventual ganador juegan otro minitorneo para determinar el segundo lugar, puede verse como un ejemplo de este método. [ 5 ] La aplicación de esta optimización a heapsort produce el algoritmo heapselect , que puede seleccionar elk{\displaystyle k}el valor más pequeño en el tiempoO(norte+kregistro⁡norte){\displaystyle O(n+k\log n)}. [ 6 ] Esto es rápido cuandok{\displaystyle k}es pequeño en relación connorte{\displaystyle n}pero degenera enO(norteregistro⁡norte){\displaystyle O(n\log n)}para valores mayores dek{\displaystyle k}, como la elecciónk=norte/2{\displaystyle k=n/2}utilizado para el cálculo de la mediana.

Pivote

Muchos métodos de selección se basan en elegir un elemento "pivote" especial de la entrada y utilizar comparaciones con este elemento para dividir el resto.norte−1{\displaystyle n-1}valores de entrada en dos subconjuntos: el conjuntoL{\displaystyle L}de elementos menores que el pivote y el conjuntoR{\displaystyle R}de elementos mayores que el pivote. El algoritmo puede entonces determinar dóndek{\displaystyle k}Se debe encontrar el valor más pequeño, basándose en una comparación dek{\displaystyle k}con los tamaños de estos conjuntos. En particular, sik≤|L|{\displaystyle k\leq |L|}, elk{\displaystyle k}El valor más pequeño está enL{\displaystyle L}y se puede encontrar recursivamente aplicando el mismo algoritmo de selección aL{\displaystyle L}. Sik=|L|+1{\displaystyle k=|L|+1}, entonces elk{\displaystyle k}El valor más pequeño es el pivote y se puede devolver inmediatamente. En el caso restante, elk{\displaystyle k}El valor más pequeño está enR{\displaystyle R}y más específicamente es el elemento en posiciónk−|L|−1{\displaystyle k-|L|-1}deR{\displaystyle R}Se puede encontrar aplicando un algoritmo de selección recursivamente, buscando el valor en esta posición enR{\displaystyle R}. [ 7 ]

Al igual que con el algoritmo quicksort basado en pivoteo relacionado , la partición de la entrada enL{\displaystyle L}yR{\displaystyle R}puede hacerse creando nuevas colecciones para estos conjuntos, o mediante un método que particione un tipo de datos de lista o matriz dado in situ. 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 esO(norte){\displaystyle O(n)}[ 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 comoO(norte2){\displaystyle O(n^{2})}. [ 4 ]

  • Si el punto de 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 se sumarían en una serie geométrica aO(norte){\displaystyle O(n)}Sin embargo , encontrar la mediana es en sí mismo un problema de selección sobre la totalidad de la entrada original. Intentar encontrarla mediante una llamada recursiva a un algoritmo de selección conduciría a una recursión infinita, ya que el tamaño del problema no disminuiría en cada llamada. [ 7 ]
  • Quickselect elige el pivote de forma uniforme y aleatoria a partir de los valores de entrada. Se puede describir como un algoritmo de poda y búsqueda , [ 9 ] una variante de quicksort , con la misma estrategia de pivoteo, pero donde quicksort realiza dos llamadas recursivas para ordenar las dos subcolecciones.L{\displaystyle L}yR{\displaystyle R}, quickselect solo realiza una de estas dos llamadas. Su tiempo previsto esO(norte){\displaystyle O(n)}. [ 2 ] [ 7 ] [ 9 ] Para cualquier constantedo{\displaystyle C}, la probabilidad de que su número de comparaciones superedonorte{\displaystyle Cn}es superexponencialmente pequeño endo{\displaystyle C}. [ 10 ]
  • El algoritmo Floyd-Rivest , una variación de quickselect, elige un pivote mediante el muestreo aleatorio de un subconjunto der{\displaystyle r}valores de datos, para algún tamaño de muestrar{\displaystyle r}y luego seleccionando recursivamente dos elementos ligeramente por encima y por debajo de la posiciónrk/norte{\displaystyle rk/n}de la muestra para usar como pivotes. Con esta elección, es probable quek{\displaystyle k}está intercalado entre los dos pivotes, de modo que después de pivotar solo queda una pequeña cantidad de valores de datos entre los pivotes para una llamada recursiva. Este método puede lograr una cantidad esperada de comparaciones que esnorte+min(k,norte−k)+o(norte){\displaystyle n+\min(k,nk)+o(n)}. [ 11 ] En su trabajo original, Floyd y Rivest afirmaron que elo(norte){\displaystyle o(n)}El plazo podría hacerse tan pequeño comoO(norte){\displaystyle O({\sqrt {n}})}mediante un esquema de muestreo recursivo, pero se ha cuestionado la corrección de su análisis. [ 12 ] [ 13 ] En cambio, un análisis más riguroso ha demostrado que una versión de su algoritmo lograO(norteregistro⁡norte){\displaystyle O({\sqrt {n\log n}})}para este término. [ 14 ] Aunque el análisis habitual tanto de quickselect como del algoritmo de Floyd-Rivest asume el uso de un generador de números aleatorios verdaderos , se ha demostrado que una versión del algoritmo de Floyd-Rivest que utiliza un generador de números pseudoaleatorios inicializado con solo una cantidad logarítmica de bits aleatorios verdaderos se ejecuta en tiempo lineal con alta probabilidad. [ 15 ]
Visualización de la selección del pivote 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 ascendente de arriba a abajo. Si sus medianas (los puntos verdes y morados en la fila central) se ordenan en orden ascendente de izquierda a derecha, y la mediana de medianas se elige como pivote, entonces3norte/10{\displaystyle 3n/10}Los elementos del cuadrante superior izquierdo serán menores que el pivote, y el3norte/10{\displaystyle 3n/10}Los elementos del cuadrante inferior derecho serán mayores que el punto de pivote, lo que demuestra que muchos elementos se eliminarán al pivotar.
  • 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 se llama a sí mismo recursivamente para encontrar la mediana de estosnorte/5{\displaystyle n/5}medianas. Usando la mediana resultante de las medianas como pivote se obtiene una partición conmáximo(|L|,|R|)≤7norte/10{\displaystyle \max(|L|,|R|)\leq 7n/10}Por lo tanto , un problema ennorte{\displaystyle n}elementos se reduce a dos problemas recursivos ennorte/5{\displaystyle n/5}elementos (para encontrar el pivote) y como máximo7norte/10{\displaystyle 7n/10}elementos (después de usar el pivote). El tamaño total de estos dos subproblemas recursivos es como máximo9norte/10{\displaystyle 9n/10}, lo que permite analizar el tiempo total como una serie geométrica que se suma aO(norte){\displaystyle O(n)}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 suO(norte){\displaystyle O(n)}Las limitaciones de tiempo hacen que sea más lento que quickselect en la práctica, [ 3 ] [ 9 ] e incluso más lento que la ordenación para entradas de tamaño moderado. [ 4 ]
  • Los algoritmos híbridos como introselect pueden utilizarse para lograr el rendimiento práctico de quickselect con una alternativa a las medianas de las medianas que garantiza el peor caso.O(norte){\displaystyle O(n)}tiempo. [ 17 ]

Fábricas

Los algoritmos de selección deterministas con el menor número conocido de comparaciones, para valores dek{\displaystyle k}que están lejos de1{\displaystyle 1}onorte{\displaystyle n}, 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ños. 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 estos ó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 "desperdiciados" 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 eventualmente obtener un orden parcial en el que un elemento (elk{\displaystyle k}el más pequeño) es más grande que algunosk−1{\displaystyle k-1}otros elementos y más pequeños que otronorte−k{\displaystyle nk}otros. Un diseño cuidadoso de estas fábricas conduce a un algoritmo que, cuando se aplica a la búsqueda de la mediana, utiliza como máximo2.942norte{\displaystyle 2.942n}comparaciones. Para otros valores dek{\displaystyle k}, el número de comparaciones es menor. [ 19 ]

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 utilizando un número lineal de comparaciones requiereΩ(registro⁡registro⁡norte){\displaystyle \Omega (\log \log n)}pasos paralelos, incluso para seleccionar el mínimo o el máximo. [ 20 ] Posteriormente, los investigadores encontraron algoritmos paralelos para la selección enO(registro⁡registro⁡norte){\displaystyle O(\log \log n)}pasos, que coinciden con este límite. [ 21 ] [ 22 ] En un modelo de árbol de comparación paralelo aleatorio es posible realizar la selección en un número limitado de pasos y un número lineal de comparaciones. [ 23 ] En el modelo de RAM paralelo más realista de computación, con acceso a memoria de lectura exclusiva y escritura exclusiva, la selección se puede realizar en tiempoO(registro⁡norte){\displaystyle O(\log n)}conO(norte/registro⁡norte){\displaystyle O(n/\log n)}procesadores, lo cual es óptimo tanto en tiempo como en número de procesadores. [ 24 ] Con acceso concurrente a memoria, en general es posible un tiempo paralelo ligeramente más rápido , [ 25 ] y elregistro⁡norte{\displaystyle \log n}El término en el límite de tiempo puede ser reemplazado porregistro⁡k{\displaystyle \log k}. [ 26 ]

Estructuras de datos sublineales

Cuando los datos ya están organizados en una estructura de datos , es posible realizar una selección en un tiempo sublineal con respecto al número de valores. Como un caso simple de esto, para datos ya ordenados en una matriz, seleccionar elk{\displaystyle k}El elemento n se puede obtener mediante una única búsqueda en la matriz, en tiempo constante. [ 27 ] Para valores organizados en una matriz bidimensional de tamañometro×norte{\displaystyle m\times n}Con filas y columnas ordenadas , la selección se puede realizar en el tiempoO(metroregistro⁡(2norte/metro)){\displaystyle O{\bigl (}m\log(2n/m){\bigr )}}o más rápido cuandok{\displaystyle k}es pequeño en relación con las dimensiones de la matriz. [ 27 ] [ 28 ] Para una colección demetro{\displaystyle m}matrices ordenadas unidimensionales, conki{\displaystyle k_{i}}artículos menores que el artículo seleccionado en eli{\displaystyle i}matriz , el tiempo esO(metro+∑i=1metroregistro⁡(ki+1)){\textstyle O{\bigl (}m+\sum _{i=1}^{m}\log(k_{i}+1){\bigr )}}. [ 28 ]

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

Para una colección de valores de datos que experimentan inserciones y eliminaciones dinámicas, el árbol de estadísticas de orden aumenta una estructura de árbol de búsqueda binaria autoequilibrada con una cantidad constante de información adicional por nodo del árbol, lo que permite inserciones, eliminaciones y consultas de selección que solicitan lak{\displaystyle k}el elemento en el conjunto actual se realizará enO(registro⁡norte){\displaystyle O(\log n)}tiempo por operación. [ 2 ] Más allá del modelo de comparación de computación, 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 en ambosnorte{\displaystyle n}yk{\displaystyle k}para resolver consultas de selección exactamente para datos dinámicos, pero el método count-min se puede utilizar para resolver consultas de selección aproximadamente, al encontrar un valor cuya posición en el orden de los elementos (si se añadiera a ellos) estaría dentro deεnorte{\displaystyle \varepsilon n}pasos dek{\displaystyle k}, para un boceto cuyo tamaño está dentro de factores logarítmicos de1/ε{\displaystyle 1/\varepsilon }. [ 33 ]

límites inferiores

ElO(norte){\displaystyle O(n)}El tiempo de ejecución de los algoritmos de selección descritos anteriormente es necesario, ya que un algoritmo de selección que puede procesar entradas en un orden arbitrario debe tomar 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 podría generar una respuesta incorrecta. [ 28 ] Más allá de este argumento simple, se ha realizado 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.

Seleccionar el mínimo denorte{\displaystyle n}Los valores requierennorte−1{\displaystyle n-1}comparaciones, porque lanorte−1{\displaystyle n-1}Los valores que no se seleccionan deben haber sido determinados como no mínimos, al ser los mayores en alguna comparación, y ningún par de estos valores puede ser el mayor en la misma comparación. El mismo argumento se aplica simétricamente a la selección del máximo. [ 14 ]

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 ajustado para 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úmeropag{\displaystyle p}de comparaciones que involucran el valor más pequeño que produce un algoritmo para este problema. Cada una de laspag{\displaystyle p}Los elementos que se compararon con el valor más pequeño son candidatos para el segundo más pequeño, ypag−1{\displaystyle p-1}De estos valores, debe encontrarse uno mayor que otro valor en una segunda comparación para poder descartarlos como segundos más pequeños.norte−1{\displaystyle n-1}valores siendo mayores en al menos una comparación, ypag−1{\displaystyle p-1}Los valores son mayores en al menos dos comparaciones, hay un total de al menosnorte+pag−2{\displaystyle n+p-2}comparaciones. Un argumento adversario , en el que el resultado de cada comparación se elige para maximizarpag{\displaystyle p}(sujeto a la coherencia con al menos un ordenamiento posible) en lugar de por los valores numéricos de los elementos dados, muestra que es posible forzarpag{\displaystyle p} to be at least log2⁡n{\displaystyle \log _{2}n}. Therefore, the worst-case number of comparisons needed to select the second smallest is n+⌈log2⁡n⌉−2{\displaystyle n+\lceil \log _ {2}n\rceil -2}, the same number that would be obtained by holding a single-elimination tournament with a run-off tournament among the values that lost to the smallest value. However, the expected number of comparisons of a randomized selection algorithm can be better than this bound; for instance, selecting the second-smallest of six elements requires seven comparisons in the worst case, but may be done by a randomized algorithm with an expected number of 6.5 comparisons.[14]

More generally, selecting the k{\displaystyle k}th element out of n{\displaystyle n} requires at least n+min(k,n−k)−O(1){\displaystyle n+\min(k,nk)-O(1)} comparisons, in the average case, matching the number of comparisons of the Floyd–Rivest algorithm up to its o(n){\displaystyle o(n)} term. The argument is made directly for deterministic algorithms, with a number of comparisons that is averaged over all possible permutations of the input values.[1] By Yao's principle, it also applies to the expected number of comparisons for a randomized algorithm on its worst-case input.[34]

For deterministic algorithms, it has been shown that selecting the k{\displaystyle k}th element requires (1+H(k/n))n+Ω(n){\displaystyle {\bigl (}1+H(k/n){\bigr )}n+\Omega ({\sqrt {n}})} comparisons, where H(x)=xlog2⁡1x+(1−x)log2⁡11−x{\displaystyle H(x)=x\log _{2}{\frac {1}{x}}+(1-x)\log _{2}{\frac {1}{1-x}}} is the binary entropy function.[35] The special case of median-finding has a slightly larger lower bound on the number of comparisons, at least (2+ε)n{\displaystyle (2+\varepsilon)n}, for ε≈2−80{\displaystyle \varepsilon \approx 2^{-80}}.[36]

Exact numbers of comparisons

Finding the median of five values using six comparisons. Each step shows the comparisons to be performed next as yellow line segments, and a Hasse diagram of the order relations found so far (with smaller=lower and larger=higher) as blue line segments. The red elements have already been found to be greater than three others and so cannot be the median. The larger of the two elements in the final comparison is the median.

Knuth supplies the following triangle of numbers summarizing pairs of n{\displaystyle n} and k{\displaystyle k} for which the exact number of comparisons needed by an optimal selection algorithm is known. The n{\displaystyle n}th row of the triangle (starting with n=1{\displaystyle n=1} in the top row) gives the numbers of comparisons for inputs of n{\displaystyle n} values, and the k{\displaystyle k}th number within each row gives the number of comparisons needed to select the k{\displaystyle k}th smallest value from an input of that size. The rows are symmetric because selecting the k{\displaystyle k}th smallest requires exactly the same number of comparisons, in the worst case, as selecting the k{\displaystyle k}el más grande. [ 14 ]

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, las entradas de la mitad izquierda de cada fila se pueden encontrar utilizando la fórmulanorte−k+(k−1)⌈registro2⁡(norte+2−k)⌉.{\displaystyle n-k+(k-1){\bigl \lceil }\log _{2}(n+2-k){\bigr \rceil }.}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 utilizando un torneo de eliminación simple y luego utiliza 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 alk{\displaystyle k}el más pequeño. [ 14 ] [ 37 ] Se demostró que algunas de las entradas más grandes eran óptimas mediante una búsqueda por computadora. [ 14 ] [ 38 ]

Soporte de idiomas

Muy pocos lenguajes tienen soporte integrado para la selección general, aunque muchos proporcionan herramientas para encontrar el elemento más pequeño o más grande de una lista. Excepciones notables son las bibliotecas estándar de C++ y Rust . La biblioteca de plantillas estándar de C++ proporciona un nth_elementmétodo con plantilla que garantiza un tiempo lineal esperado. [ 3 ] La biblioteca estándar de Rust proporciona múltiples variantes de la select_nth_unstablefunción miembro para el slicetipo de datos. Todas estas variantes tienen un tiempo de ejecución lineal garantizado para todas las entradas. [ 39 ]

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 almacenark{\displaystyle k}elementos, e inicializado al primerok{\displaystyle k}elementos en la colección. Luego, cada elemento subsiguiente de la colección puede reemplazar el elemento más grande o más pequeño en el montón si es menor o mayor que este elemento. El uso de memoria del algoritmo es superior a heapselect (el primero solo contienek{\displaystyle k}elementos en memoria a la vez, mientras que el segundo requiere manipular todo el conjunto de datos en memoria). El tiempo de ejecución depende del orden de los datos. El mejor caso esO((norte−k)+kregistro⁡k){\displaystyle O((n-k)+k\log k)}para datos ya ordenados. El peor caso esO(norteregistro⁡k){\displaystyle O(n\log k)}para datos ordenados en orden inverso. En promedio, es probable que haya pocas actualizaciones de la pila 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 genera, en promedio, 10 009 401 comparaciones. [ 40 ]

Desde 2017, Matlab ha incluido maxk()funciones mink()que devuelven el máximo (mínimo)k{\displaystyle k}valores en un vector así como sus índices. La documentación de Matlab no especifica qué algoritmo usan estas funciones ni cuál es su tiempo de ejecución. [ 41 ]

Historia

Quickselect fue presentado sin análisis por Tony Hoare en 1965, [ 42 ] y analizado por primera vez en un informe técnico de 1971 por Donald Knuth . [ 11 ] El primer algoritmo de selección determinista de 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 ] Ellos rastrean la formulación del problema de selección hasta el trabajo de Charles L. Dodgson (más 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 ] [ 43 ] y hasta el 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

Referencias

  1. 1 2 Cunto, Walter; Munro, J. Ian (1989). "Selección de casos promedio" . Journal of the ACM . 36 (2): 270– 279. doi : 10.1145/62044.62047 . MR 1072421. S2CID 10947879 .  
  2. 1 2 3 4 5 6 7 8 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 orden dinámico", págs. 339–345
  3. 1 2 3 4 Skiena, Steven S. (2020). "17.3: Mediana y selección". The Algorithm Design Manual . Textos en Ciencias de la Computación (Tercera ed.). Springer. págs. 514–516 . doi : 10.1007/978-3-030-54256-6 . ISBN   978-3-030-54255-9. MR 4241430 . S2CID 22382667 .  
  4. 1 2 3 4 5 Erickson, Jeff (junio de 2019). "1.8: Selección en tiempo lineal". Algoritmos . págs. 35–39 . 
  5. 1 2 3 4 5 6 Blum, Manuel ; Floyd, Robert W .; Pratt, Vaughan ; Rivest, Ronald L.; Tarjan , Robert E. (1973). "Límites de tiempo para la selección" (PDF) . Journal of Computer and System Sciences . 7 (4): 448– 461. doi : 10.1016/S0022-0000(73)80033-9 . MR 0329916 . 
  6. ↑ Brodal, Gerth Stølting (2013). "Una revisión sobre colas de prioridad". En Brodnik, Andrej; López-Ortiz, Alejandro; Raman, Venkatesh; Viola, Alfredo (eds.). Estructuras de datos, flujos y algoritmos eficientes en espacio: artículos en honor a J. Ian Munro con motivo de su 66.º cumpleaños . Lecture Notes in Computer Science. Vol. 8066. Springer. pp. 150–163 . doi : 10.1007/978-3-642-40273-9_11 . ISBN   978-3-642-40272-2.
  7. 1 2 3 4 Kleinberg, Jon ; Tardos, Éva (2006). "13.5 Divide y vencerás aleatorizado: búsqueda de la mediana y ordenación rápida". Diseño de algoritmos . Addison-Wesley. págs. 727–734 . ISBN  9780321295354.
  8. ↑ Por ejemplo, Cormen et al. utilizan una partición de matriz in situ, mientras que Kleinberg y Tardos describen la entrada como un conjunto y utilizan un método que la divide en dos nuevos conjuntos.
  9. 1 2 3 4 Goodrich, Michael T. ; Tamassia, Roberto (2015). "9.2: Selección". Diseño y aplicaciones de algoritmos . 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) . Journal of Computer and System Sciences . 29 (1): 1– 7. doi : 10.1016/0022-0000(84)90009-6 . MR 0761047 . Devroye, Luc (2001). "Sobre el tiempo probabilístico del peor caso de 'encontrar'" (PDF) . Algorithmica . 31 (3): 291– 303. doi : 10.1007/s00453-001-0046-2 . MR 1855252 . S2CID 674040 .  
  11. 1 2 Floyd, Robert W. ; Rivest, Ronald L. (marzo de 1975). "Límites de tiempo esperados para la selección" . Communications of the ACM . 18 (3): 165– 172. doi : 10.1145/360680.360691 . S2CID 3064709 . Véase también "Algoritmo 489: el algoritmo SELECT—para encontrar eli{\displaystyle i}el más pequeño denorte{\displaystyle n}elementos", pág. 173, doi : 10.1145/360680.360694 .
  12. ↑ Brown, Theodore (septiembre de 1976). "Comentario 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" . Communications of the ACM . 26 (11): 878– 881. doi : 10.1145/182.358440 . MR 0784120. S2CID 3211474 .  
  14. 1 2 3 4 5 6 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" . Journal of the ACM . 40 (3): 454– 476. doi : 10.1145/174130.174132 . MR 1370358. S2CID 17956460 .  
  16. ↑ Gurwitz, Chaya (1992). "Sobre la enseñanza de algoritmos para encontrar la mediana". 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 clasificación y selección introspectivos". Software: Practice and Experience . 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). "Finding the mediana". Journal of Computer and System Sciences . 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". SIAM Journal on Computing . 28 (5): 1722– 1758. doi : 10.1137/S0097539795288611 . MR 1694164. S2CID 2633282 .  
  20. ↑ Valiant, Leslie G. (1975). "Paralelismo en problemas de comparación". SIAM Journal on Computing . 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 complejidadO(registro⁡registro⁡norte){\displaystyle O(\log \log n)}". Revista de Ciencias de la Computación y de Sistemas . 38 (1): 125– 133. doi : 10.1016/0022-0000(89)90035-4 . MR 0990052 . 
  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 paralelos probabilísticos para ordenación y selección". SIAM Journal on Computing . 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 . Lecture Notes in Computer Science. Vol. 711. Springer. pp. 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 rango pequeño 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. 1 2 Frederickson, Greg N.; Johnson, Donald B. (1984). "Selección y clasificación generalizadas: matrices ordenadas". SIAM Journal on Computing . 13 (1): 14– 30. doi : 10.1137/0213002 . MR 0731024 . 
  28. 1 2 3 4 Kaplan, Haim; Kozma, László; Zamir, Or; Zwick, Uri (2019). "Selección de montones, matrices ordenadas por filas yincógnita+Y{\displaystyle X+Y}usando montones blandos". En Fineman, Jeremy T.; Mitzenmacher, Michael (eds.). Segundo simposio sobre simplicidad en algoritmos, SOSA 2019, 8 al 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 .
  29. ↑ Frederickson, Greg N. (1993). "Un algoritmo óptimo para la selección en un min-heap" . Information and Computation . 104 (2): 197– 214. doi : 10.1006/inco.1993.1030 . MR 1221889 . 
  30. ↑ Eppstein, David (1999). "Encontrar elk{\displaystyle k}caminos más cortos". SIAM Journal on Computing . 28 (2): 652– 673. doi : 10.1137/S0097539795290477 . MR 1634364 . 
  31. ↑ Babenko, Maxim; Kolesnichenko, Ignat; Smirnov, Ivan (2019). "Montículo en cascada: hacia extracciones óptimas en tiempo". Theory of Computing Systems . 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 enteros dinámicos con rango óptimo, selección y búsqueda de predecesores". 55.º Simposio Anual IEEE sobre Fundamentos de la Informática, FOCS 2014, Filadelfia, PA, 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 de 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 comparaciones 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 requiere2norte{\displaystyle 2n}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  0-89791-151-2.
  36. ↑ Dor, Dorit ; Zwick, Uri (2001). "La selección de la mediana requiere(2+ε)norte{\displaystyle (2+\varepsilon )N}comparaciones". SIAM Journal on Discrete Mathematics . 14 (3): 312– 325. doi : 10.1137/S0895480199353895 . MR 1857348 . 
  37. ^ Hadián, Abdollah; Sobel, Milton (mayo de 1969). Seleccionando elt{\displaystyle t}-ésimo mayor utilizando comparaciones binarias sin errores (Informe). Informes técnicos de la Escuela de Estadística. Vol.  121. Universidad de Minnesota. hdl : 11299/199105 .
  38. ↑ Gasarch, William ; Kelly, Wayne; Pugh, William (julio de 1996). "Encontrar eli{\displaystyle i}el más grande denorte{\displaystyle n}para pequeñosi,norte{\displaystyle i,n}". ACM SIGACT News . 27 (2): 88– 96. doi : 10.1145/235767.235772 . S2CID 3133332 . 
  39. ↑ "Segmento de tipo primitivo" . La biblioteca estándar de Rust . Consultado el 12 de octubre de 2025 .
  40. ↑ "Código fuente del paquete heapq" . Biblioteca de Python . Consultado el 6 de agosto de 2023 .; véase también la comparación vinculada del rendimiento del algoritmo en los datos del mejor caso .
  41. ↑ "mink: Encuentra los k elementos más pequeños de un array" . Documentación de Matlab R2023a . Mathworks . Consultado el 30 de marzo de 2023 .
  42. ↑ Hoare, CAR (julio de 1961). "Algoritmo 65: Find". Communications of the ACM . 4 (7): 321– 322. doi : 10.1145/366622.366647 .
  43. ↑ Dodgson, Charles L. (1883). Torneos de tenis sobre césped: El verdadero método de asignación de premios con una demostración 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.
Lecturas relacionadas
6 articulos
Ciencias de la ComputaciónCiencias de la ComputaciónÁreas fundamentales de la informática La informática es el estudio de la computación , la información y la automatización . [1] [2] [3] La informát...AlgoritmoAlgoritmoEn matemáticas y ciencias de la computación , un algoritmo ( / ˈ æ l ɡ ə r ɪ ð əm / ⓘ ) es una secuencia finita deinstruccionesmatemáticamente rigu...Estadística de pedidosEstadística de pedidosEn estadística , la estadística de orden k de una muestra estadística es igual a su valor k más pequeño. [1] Junto con las estadísticas de rango , ...Máximo y mínimoMáximo y mínimoEn análisis matemático , el máximo y el mínimo [ a ] de una función son, respectivamente, el mayor y el menor valor que toma la función. Conocidos ...MedianaEncontrar la mediana en conjuntos de datos con un número par e impar de valores La mediana de un conjunto de números es el valor que separa la mita...Máximo y mínimoMáximo y mínimoEn análisis matemático , el máximo y el mínimo [a] de una función son, respectivamente, el valor más grande y más pequeño que toma la función. Cono...