Algoritmo de selección

En ciencias de la computación , un algoritmo de selección es un algoritmo para encontrar el k-ésimo elemento más grande en una matriz (dicho elemento se denomina estadístico de k-ésimo orden ). Los casos especiales de este algoritmo son encontrar el elemento mínimo , el elemento máximo y la mediana . Hay un algoritmo que está garantizado para resolver el problema de elegir el k-ésimo elemento más grande en O( n ).

Selección por clasificación

El problema de la selección puede reducirse a la clasificación . De hecho, puede ordenar una matriz y luego tomar el elemento que necesita en orden. Esto es efectivo cuando la elección debe hacerse varias veces: luego puede ordenar la matriz en O ( n log n ) y luego seleccionar elementos de ella. Sin embargo, si la elección debe hacerse una vez, este algoritmo puede ser excesivamente largo.

Algoritmo lineal para encontrar el mínimo (máximo)

Obviamente, cómo encontrar el mínimo (máximo) en una matriz dada en tiempo lineal:

asignar inicialmente $min=a[0];$
Para cada elemento , ejecute: si , asigne . $ai]$ $min>a[i]$ $mín=a[i]$

Un algoritmo lineal promedio para encontrar el estadístico de k -ésimo orden

Existe un algoritmo para encontrar la estadística de orden k -ésimo basado en el algoritmo de clasificación rápida que se ejecuta en O( n ) en promedio.

La idea del algoritmo es que la matriz se divide en dos partes en relación con un elemento seleccionado aleatoriamente (equiprobablemente): los elementos más pequeños que el seleccionado caen en una parte, el resto en la otra (esta operación se realiza para , en al final del mismo el elemento seleccionado está en posición ). Si hay exactamente elementos en la primera parte ( ), entonces el elemento seleccionado es el deseado, si , entonces el algoritmo se ejecuta recursivamente para la primera parte de la matriz, de lo contrario, para la segunda (en el último caso, para el siguiente iteración, se resta de ). Las llamadas recursivas conducen a una disminución exponencial del tamaño de la matriz procesada con cada iteración y, por esta razón, el tiempo de ejecución del algoritmo es . $En)$ $j$ $k-1$ $j=k$ ${\ estilo de visualización j> k}$ $k$ $j$ $En)$

Algoritmo BFPRT (determinista lineal)

BFPRT-Algorithm le permite encontrar las estadísticas de k -ésimo orden garantizadas en O( n ). Nombrado en honor a sus inventores: Manual Blum, Robert W. Floyd, Vaughan R. Pratt , Ronald L. Rivest y Robert Endre T arjan . Se utiliza con una lista bastante larga de elementos, más de 800 elementos.

Cómo funciona

Entrada: número que representa el -ésimo elemento. $i$ $i$

La lista se divide en subconjuntos de elementos, 5 elementos cada uno (excepto el último subconjunto). El número de elementos de los subconjuntos puede ser superior a 5 y debe ser impar en todo caso. Sin embargo, si divide la lista en subconjuntos de 3 elementos, el tiempo de ejecución no será lineal.
Cada subconjunto se clasifica utilizando un algoritmo de clasificación adecuado .
Sea el conjunto de medianas formadas en subconjuntos después de ordenar. Encuentre recursivamente la mediana en — mediana de medianas. Llamemosla . $S$ $S$ $s$
- La estructura resultante después del paso 3 tiene la siguiente característica:
  - Una cuarta parte de todos los elementos tienen una clave de todos modos . (Un subconjunto del conjunto ) $<s$ $S_{1}$
  - Una cuarta parte de todos los elementos tienen una clave de todos modos . (Un subconjunto del conjunto ) $>s$ $S_{2}$
Ahora la lista se divide con respecto a la mediana s en 2 subconjuntos y . En este caso, solo la mitad de todos los elementos deben compararse con s, ya que dos cuartas partes de los elementos ya están ordenados en relación con s. Como resultado, cada uno de los subconjuntos contiene un máximo de 3/4 de todos los elementos (el mínimo es 1/4 de todos los elementos). $S_{1}$ $S_{2}$ $S_{1}$ $S_{2}$
Si un:
- $yo=|S_{1}|+1$ , luego se encuentra el elemento deseado: esta es la mediana de las medianas $s$
- $i\leq |S_{1}|$ , entonces el algoritmo se llama recursivamente en el conjunto $S_{1}$
- en cualquier otro caso, el algoritmo se llama recursivamente en el conjunto $S_{2}$

Tiempo de actividad garantizado

Con cada llamada recursiva , el algoritmo le permite descartar al menos una cuarta parte de todos los elementos. Esto proporciona un límite superior en el tiempo de ejecución lineal garantizado para un algoritmo determinista , ya que se expresa mediante la relación de recurrencia . En general, si los subconjuntos son de tamaño , el tiempo de ejecución se expresa como . $T(n)=O(n)+T\left({\frac {n}{5}}\right)+T\left({{\frac {7}{10}}n}\right )$ ${\ estilo de visualización 2k+1}$ $T(n)=O(n)+T\left({\frac {n}{2k+1}}\right)+T\left({{\frac {3k+1}{4k+2 }}n}\derecho)$

Literatura

Volker Heun. Algoritmos básicos = Grundlegende Algorithmen. - 1ª ed. - Múnich: Vieweg Verlag, 2000. - Pág. 86. - ISBN 3-528-03140-9 .
Límites de tiempo para la selección por Manual Blum, Robert W. Floyd, Vaughan Pratt, Ronald L. Rivest y Robert E. Tarjan. Journal of Computer and System Sciences 7.4 de agosto de 1973 , 448-460