LISTAS RELACIONADAS CON LAS MATEMÁTICAS - ALGORITMOS

algoritmo de selección es un algoritmo para encontrar el késimo número más pequeño en una lista o matriz ; un número tal se llama el k ésimo estadísticos de orden . Esto incluye los casos de encontrar los elementos mínimo , máximo y mediano . Existen algoritmos de selección de O ( n ) tiempo (peor tiempo lineal), y el rendimiento sublineal es posible para datos estructurados; en el extremo, O (1) para una matriz de datos ordenados. La selección es un subproblema de problemas más complejos como el vecino más cercano yproblemas de camino más corto . Muchos algoritmos de selección se derivan generalizando un algoritmo de clasificación y, a la inversa, algunos algoritmos de clasificación pueden derivarse como aplicación repetida de selección.

El caso más simple de un algoritmo de selección es encontrar el elemento mínimo (o máximo) iterando a través de la lista, haciendo un seguimiento del mínimo en ejecución (el mínimo hasta ahora) (o máximo) y puede verse como relacionado con el tipo de selección . Por el contrario, el caso más difícil de un algoritmo de selección es encontrar la mediana. De hecho, se puede usar un algoritmo especializado de selección de mediana para construir un algoritmo de selección general, como en la mediana de las medianas . El algoritmo de selección más conocido es quickselect , que está relacionado con quicksort ; Al igual que QuickSort, tiene (asintóticamente) un rendimiento promedio óptimo, pero un rendimiento pobre en el peor de los casos, aunque también se puede modificar para proporcionar un rendimiento óptimo en el peor de los casos.

Selección ordenando [ editar ]

Al ordenar la lista o matriz y luego seleccionar el elemento deseado, la selección se puede reducir a la clasificación . Este método es ineficiente para seleccionar un solo elemento, pero es eficiente cuando se necesitan hacer muchas selecciones desde una matriz, en cuyo caso solo se necesita una clasificación costosa inicial, seguida de muchas operaciones de selección baratas: O (1) para una matriz , aunque la selección es O ( n ) en una lista vinculada, incluso si está ordenada, debido a la falta de acceso aleatorio . En general, la ordenación requiere un tiempo O ( n log n ), donde n es la longitud de la lista, aunque es posible un límite inferior con algoritmos de ordenación no comparativos como la ordenación por radix ycontando tipo .

En lugar de ordenar toda la lista o matriz, uno puede usar la ordenación parcial para seleccionar los k elementos más pequeños o k más grandes. El k ésimo más pequeño (resp., K elemento más grande) es entonces el más grande (resp., Elemento más pequeño) de la lista parcialmente ordenada; esto toma O (1) para acceder en una matriz y O ( k ) para acceder en una lista.

Clasificación parcial desordenada [ editar ]

Si la ordenación parcial se relaja para que se devuelvan los k elementos más pequeños, pero no en orden, se puede eliminar el factor de O ( k log k ). Se requiere una selección máxima adicional (tomar tiempo O ( k )), pero dado que$${\ displaystyle k \ leq n}, esto todavía produce complejidad asintótica de O ( n ). De hecho, los algoritmos de selección basados ​​en particiones producen tanto el k como el elemento más pequeño y los k elementos más pequeños (con otros elementos que no están en orden). Esto se puede hacer en O ( n ) tiempo: la complejidad promedio de la selección rápida y la complejidad del peor de los algoritmos de selección basados ​​en particiones refinadas.

Por el contrario, dado un algoritmo de selección, uno puede obtener fácilmente una ordenación parcial desordenada ( k elementos más pequeños, no en orden) en el tiempo O ( n ) iterando a través de la lista y registrando todos los elementos menos que el elemento k . Si esto resulta en menos de k  - 1 elementos, cualquier elemento restante es igual al k ésimo elemento. Se debe tener cuidado, debido a la posibilidad de igualdad de elementos: no se deben incluir todos los elementos menores o iguales que el elemento k , ya que los elementos mayores que el elemento k también pueden ser iguales.

Por lo tanto, la ordenación parcial desordenada ( elementos k más bajos , pero no ordenados) y la selección del elemento k th son problemas muy similares. No solo tienen la misma complejidad asintótica, O ( n ), sino que una solución para cualquiera de ellos puede convertirse en una solución para el otro mediante un algoritmo sencillo (encontrar un máximo de k elementos o filtrar elementos de una lista debajo de un corte del valor del elemento k ).

Ordenación por selección parcial [ editar ]

Un ejemplo simple de selección mediante ordenación parcial es utilizar la ordenación de selección parcial .

El algoritmo de tiempo lineal obvio para encontrar el mínimo (máximo resp.) - iterando sobre la lista y haciendo un seguimiento del elemento mínimo (máximo resp.) Hasta ahora - puede verse como una selección parcial que selecciona el 1 elemento más pequeño. Sin embargo, muchos otros tipos parciales también se reducen a este algoritmo para el caso k  = 1, como un tipo de montón parcial.

De manera más general, una selección de selección parcial produce un algoritmo de selección simple que toma tiempo O ( kn ). Esto es asintóticamente ineficiente, pero puede ser suficientemente eficiente si k es pequeño y es fácil de implementar. Concretamente, simplemente encontramos el valor mínimo y lo movemos al principio, repitiendo en la lista restante hasta que hayamos acumulado k elementos, y luego devolvemos el k elemento th. Aquí hay un algoritmo de selección parcial basado en el algoritmo:

 selección de función (lista [1..n], k)
      para i de 1 a k
         minIndex = i
         minValue = list [i]
         para j de i + 1 a n
              si list [j] 
                 minIndex = j
                 minValue = list [j]
                 intercambiar lista [i] y lista [minIndex]
     lista de retorno [k]

Selección basada en particiones [ editar ]

Más información: Quickselect

El rendimiento lineal se puede lograr mediante un algoritmo de selección basado en particiones, básicamente una selección rápida . Quickselect es una variante de quicksort : en ambos se elige un pivote y luego se reparten los datos, pero mientras Quicksort se repite en ambos lados de la partición, Quickselect solo se repite en un lado, es decir, en el lado en el que se encuentra el elemento k deseado . Al igual que con Quicksort, tiene un rendimiento promedio óptimo, en este caso lineal, pero un rendimiento pobre en el peor de los casos, en este caso cuadrático. Esto ocurre, por ejemplo, tomando el primer elemento como pivote y buscando el elemento máximo, si los datos ya están ordenados. En la práctica, esto se puede evitar eligiendo un elemento aleatorio como pivote, que produce casi ciertoRendimiento lineal. Alternativamente, se puede utilizar una estrategia pivote determinista más cuidadosa, como la mediana de las medianas . Estos se combinan en el híbrido introselect algoritmo (análogo a introsort ), que comienza con Quickselect pero cae de nuevo a la mediana de medianas si el progreso es lento, dando como resultado a la vez rápido rendimiento medio y el rendimiento óptimo del peor caso de O ( n ).

Los algoritmos basados ​​en particiones generalmente se realizan en su lugar, lo que resulta en una clasificación parcial de los datos. Se pueden hacer fuera de lugar, sin cambiar los datos originales, a costa de O ( n ) espacio adicional.

Selección mediana como estrategia de pivote [ editar ]

Más información: mediana de medianas

Se puede usar un algoritmo de selección mediana para generar un algoritmo de selección general o un algoritmo de clasificación, aplicándolo como la estrategia de pivote en Quickselect o Quicksort; si el algoritmo de selección mediana es asintóticamente óptimo (tiempo lineal), el algoritmo de selección o clasificación resultante también lo es. De hecho, no es necesaria una mediana exacta; una mediana aproximada es suficiente. En el algoritmo de selección de mediana de medianas , la estrategia de pivote calcula una mediana aproximada y la utiliza como pivote, recurriendo en un conjunto más pequeño para calcular este pivote. En la práctica, la sobrecarga del cálculo de pivote es significativa, por lo que estos algoritmos generalmente no se usan, pero esta técnica es de interés teórico en relacionar algoritmos de selección y clasificación.

En detalle, dado un algoritmo de selección mediana, uno puede usarlo como una estrategia pivote en Quickselect, obteniendo un algoritmo de selección. Si el algoritmo de selección mediana es óptimo, lo que significa O ( n ), entonces el algoritmo de selección general resultante también es óptimo, de nuevo significa lineal. Esto se debe a que Quickselect es un algoritmo de divide y vencerás , y el uso de la mediana en cada pivote significa que en cada paso el conjunto de búsqueda disminuye a la mitad, por lo que la complejidad general es una serie geométrica multiplicada por la complejidad de cada paso, y por lo tanto simplemente un tiempo constante la complejidad de un solo paso, de hecho$${\ displaystyle 2 = 1 / (1- (1/2))} veces (sumando la serie).

Del mismo modo, dado un algoritmo de selección de mediana o un algoritmo de selección general aplicado para encontrar la mediana, se puede usar como una estrategia de pivote en Quicksort, obteniendo un algoritmo de clasificación. Si el algoritmo de selección es óptimo, lo que significa O ( n ), entonces el algoritmo de clasificación resultante es óptimo, lo que significa O ( n log n ). La mediana es el mejor pivote para la clasificación, ya que divide los datos de manera uniforme y, por lo tanto, garantiza una clasificación óptima, suponiendo que el algoritmo de selección sea óptimo. Existe una ordenación análoga a la mediana de las medianas, utilizando la estrategia de pivote (mediana aproximada) en Quicksort, y de manera similar produce un Quicksort óptimo.

Clasificación incremental por selección [ editar ]

Al contrario de la selección ordenando, se puede ordenar de forma incremental por selección repetida. En resumen, la selección solo produce un único elemento, el elemento k . Sin embargo, los algoritmos prácticos de selección con frecuencia implican una clasificación parcial, o pueden modificarse para hacerlo. La selección por ordenación parcial lo hace naturalmente, ordenando los elementos hasta k , y seleccionando por partición también clasifica algunos elementos: los pivotes se ordenan en las posiciones correctas, con la kEl elemento es el pivote final, y los elementos entre los pivotes tienen valores entre los valores de pivote. La diferencia entre la selección basada en partición y la clasificación basada en partición, como en la selección rápida versus la clasificación rápida, es que en la selección se recurre solo a un lado de cada pivote, clasificando solo los pivotes ( se usa un promedio de log ( n ) pivotes), en lugar de recurrir a ambos lados del pivote.

Esto se puede usar para acelerar las selecciones posteriores en los mismos datos; en el extremo, una matriz completamente ordenada permite la selección de O (1). Además, en comparación con hacer primero una clasificación completa, la clasificación incremental por selección repetida amortiza el costo de clasificación en varias selecciones.

Para datos parcialmente ordenados (hasta k ), siempre que se registren los datos parcialmente ordenados y el índice k hasta el cual se ordenan los datos, las selecciones posteriores de j menor o igual que k pueden simplemente seleccionar el elemento j , como ya está ordenado, mientras que las selecciones de j mayores que k solo necesitan ordenar los elementos por encima de la k posición.

Para datos particionados, si la lista de pivotes está almacenada (por ejemplo, en una lista ordenada de los índices), entonces las selecciones posteriores solo necesitan seleccionar en el intervalo entre dos pivotes (los pivotes más cercanos debajo y arriba). La mayor ganancia proviene de los pivotes de nivel superior, que eliminan particiones grandes y costosas: un solo pivote cerca del medio de los datos reduce el tiempo para futuras selecciones a la mitad. La lista dinámica crecerá en las selecciones posteriores, a medida que los datos se ordenen más, e incluso se pueden pasar a una ordenación basada en particiones como base de una ordenación completa.

Uso de estructuras de datos para seleccionar en tiempo sublineal [ editar ]

Dada una lista desorganizada de datos, se requiere tiempo lineal (Ω ( n )) para encontrar el elemento mínimo, porque tenemos que examinar cada elemento (de lo contrario, podríamos perderlo). Si organizamos la lista, por ejemplo, manteniéndola ordenada en todo momento, entonces seleccionar el elemento más grande k es trivial, pero luego la inserción requiere tiempo lineal, al igual que otras operaciones como combinar dos listas.

La estrategia para encontrar una estadística de orden en tiempo sublineal es almacenar los datos de manera organizada utilizando estructuras de datos adecuadas que faciliten la selección. Dos de estas estructuras de datos son estructuras basadas en árboles y tablas de frecuencias.

Cuando solo se necesita el mínimo (o máximo), un buen enfoque es usar un montón , que puede encontrar el elemento mínimo (o máximo) en tiempo constante, mientras que todas las demás operaciones, incluida la inserción, son O (log n ) o mejor. En términos más generales, un árbol de búsqueda binaria con auto-equilibrio se puede aumentar fácilmente para que sea posible insertar un elemento y encontrar el k- ésimo elemento más grande en el tiempo O (log n ); Esto se llama un árbol de estadísticas de orden . Simplemente almacenamos en cada nodo un recuento de cuántos descendientes tiene, y lo usamos para determinar qué camino seguir. La información se puede actualizar de manera eficiente ya que agregar un nodo solo afecta los recuentos de su O (log n) ancestros, y las rotaciones de los árboles solo afectan los recuentos de los nodos involucrados en la rotación.

Otra estrategia simple se basa en algunos de los mismos conceptos que la tabla hash . Cuando conocemos el rango de valores de antemano, podemos dividir ese rango en subintervalos h y asignarlos a los cubos h . Cuando insertamos un elemento, lo agregamos al depósito correspondiente al intervalo en el que se encuentra. Para encontrar el elemento mínimo o máximo, exploramos desde el principio o el final el primer depósito no vacío y encontramos el elemento mínimo o máximo en ese depósito. . En general, para encontrar el kEn el elemento, mantenemos un recuento del número de elementos en cada cubo, luego escaneamos los cubos de izquierda a derecha sumando los recuentos hasta que encontramos el cubo que contiene el elemento deseado, luego usamos el algoritmo de tiempo lineal esperado para encontrar el elemento correcto en ese cubo

Si elegimos h de tamaño aproximadamente sqrt ( n ), y la entrada está casi distribuida uniformemente, este esquema puede realizar selecciones en el tiempo esperado de O (sqrt ( n )). Desafortunadamente, esta estrategia también es sensible a la agrupación de elementos en un intervalo estrecho, lo que puede generar cubos con un gran número de elementos (la agrupación se puede eliminar mediante una buena función hash, pero encontrar el elemento con el k valor de hash más grande no es ' t muy útil). Además, al igual que las tablas hash, esta estructura requiere el cambio de tamaño de la tabla para mantener la eficiencia a medida que se agregan elementos yn se vuelve mucho más grande que h ². Un caso útil de esto es encontrar un orden estadístico o extremo en un rango finito de datos. Usar la tabla anterior con el intervalo de cubeta 1 y mantener los recuentos en cada cubeta es muy superior a otros métodos. Tales tablas hash son como tablas de frecuencia utilizadas para clasificar los datos en estadísticas descriptivas .

Límites inferiores [ editar ]

En The Art of Computer Programming , Donald E. Knuth discutió una serie de límites inferiores para el número de comparaciones necesarias para localizar los t entradas más pequeñas de una lista no organizado de n elementos (utilizando sólo las comparaciones). Hay un límite inferior trivial de n - 1 para la entrada mínima o máxima. Para ver esto, considere un torneo donde cada juego representa una comparación. Dado que todos los jugadores, excepto el ganador del torneo, deben perder un juego antes de conocer al ganador, tenemos un límite inferior de n - 1 comparaciones.

La historia se vuelve más compleja para otros índices. Definimos$${\ displaystyle W_ {t} (n)}como el número mínimo de comparaciones requeridas para encontrar los valores t más pequeños. Knuth hace referencia a un artículo publicado por SS Kislitsyn, que muestra un límite superior en este valor:

{\ displaystyle W_ {t} (n) \ leq n-t + \ sum _ {n + 1-t

Este límite es alcanzable para t = 2 pero mejor, se conocen límites más complejos para t más grande . ^{[ cita requerida ]}

Complejidad espacial [ editar ]

La complejidad espacial requerida de la selección es O (1) almacenamiento adicional, además de almacenar la matriz en la que se realiza la selección. Dicha complejidad espacial puede lograrse mientras se preserva la complejidad óptima del tiempo O (n). ^[1]

Esta sección necesita expansión . Puedes ayudar agregándole . ( Enero 2019 )

Algoritmo de selección en línea [ editar ]

Online selección puede referirse estrechamente a calcular el k -ésimo elemento más pequeño de una corriente, en cuyo caso parcial algoritmos de ordenación (con k + O (1)) el espacio para la k elementos más pequeños hasta ahora) se pueden utilizar, pero los algoritmos basados en partición no puede ser.

Alternativamente, se puede requerir que la selección en sí misma esté en línea , es decir, un elemento solo se puede seleccionar de una entrada secuencial en la instancia de observación y cada selección, respectivamente rechazo, es irrevocable. El problema es seleccionar, bajo estas restricciones, un elemento específico de la secuencia de entrada (como, por ejemplo, el valor más grande o el más pequeño) con mayor probabilidad. Este problema puede ser abordado por el algoritmo Odds , que produce el óptimo bajo una condición de independencia; también es óptimo en sí mismo como un algoritmo con el número de cálculos lineales en la longitud de entrada.

El ejemplo más simple es el problema de la secretaria de elegir el máximo con alta probabilidad, en cuyo caso la estrategia óptima (en datos aleatorios) es rastrear el máximo en ejecución de los primeros elementos n / e y rechazarlos, y luego seleccionar el primer elemento que sea más alto que este máximo.

Problemas relacionados [ editar ]

Uno puede generalizar el problema de selección para aplicar a rangos dentro de una lista, lo que genera el problema de las consultas de rango . Se analizó la cuestión de las consultas de rango medio (cálculo de las medianas de rangos múltiples).

Soporte de idiomas [ editar ]

Muy pocos idiomas tienen soporte incorporado para la selección general, aunque muchos proporcionan facilidades para encontrar el elemento más pequeño o más grande de una lista. Una excepción notable es C ++ , que proporciona una plantilla de nth_elementmétodo con una garantía de tiempo lineal era de esperar, y también las particiones de los datos, lo que requiere que el n -ésimo elemento se clasifica en su lugar correcto, los elementos antes de la n -ésimo elemento son menos de lo que, y elementos después de la n -ésimo elemento es mayor que ella. Está implícito pero no se requiere que se base en el algoritmo de Hoare (o alguna variante) por su requisito de tiempo lineal esperado y partición de datos. ^[2] [3]

Para Perl , el módulo Sort :: Key :: Top , disponible en CPAN , proporciona un conjunto de funciones para seleccionar los n elementos superiores de una lista utilizando varios ordenamientos y procedimientos de extracción de claves personalizados. Además, el módulo Statistics :: CaseResampling proporciona una función para calcular cuantiles usando la selección rápida.

La biblioteca estándar de Python (desde 2.4) incluye heapq.nsmallest()y nlargest(), devolviendo listas ordenadas, en tiempo O ( n log k ). ^[4]

Debido a que el soporte de idioma para la clasificación es más omnipresente, el enfoque simplista de la clasificación seguido de la indexación se prefiere en muchos entornos a pesar de su desventaja en velocidad. De hecho, para los lenguajes perezosos , este enfoque simplista puede incluso lograr la mejor complejidad posible para los k más pequeños / más grandes ordenados (con el máximo / mínimo como un caso especial) si el tipo es lo suficientemente flojo ^{[ cita requerida ]} .

algoritmo de búsqueda ternario es una técnica en informática para encontrar el mínimo o el máximo de una función unimodal . Una búsqueda ternaria determina que el mínimo o el máximo no pueden estar en el primer tercio del dominio o que no puede estar en el último tercio del dominio, luego se repite en los dos tercios restantes. Una búsqueda ternaria es un ejemplo de algoritmo de divide y vencerás (ver algoritmo de búsqueda ).

La función [ editar ]

Algoritmo [ editar ]

Sea f ( x ) una función imodal en algún intervalo [ l ; r ]. Tome dos puntos m ₁ y m ₂ en este segmento: l < m ₁ < m ₂ < r . Entonces hay tres posibilidades:

• si f ( m ₁ ) < f ( m ₂ ) , entonces el máximo requerido no puede ubicarse en el lado izquierdo - [ l ; m ₁ ] . Significa que el máximo tiene más sentido mirar solo en el intervalo [ m ₁ ; r ]
• si f ( m ₁ )> f ( m ₂ ) , la situación es similar a la anterior, hasta la simetría. Ahora, el máximo requerido no puede estar en el lado derecho - [ m ₂ ; r ] , entonces vaya al segmento [ l ; m ₂ ]
• si f ( m ₁ ) = f ( m ₂ ) , entonces la búsqueda debe realizarse en [ m ₁ ; m ₂ ] , pero este caso puede atribuirse a cualquiera de los dos anteriores (para simplificar el código). Tarde o temprano, la longitud del segmento será un poco menor que una constante predeterminada, y el proceso se puede detener.

puntos de elección m ₁ y m ₂ :

• m ₁ = l + ( r - l ) / 3
• m ₂ = r - ( r - l ) / 3

Orden de tiempo de ejecución

$${\ displaystyle T (n) = T (2n / 3) + 1 = \ Theta (\ log n)}

Algoritmo recursivo [ editar ]

def  ternarySearch ( f ,  left ,  right ,  absolutePrecision ): 
    '' ' 
    left y right son los límites actuales; 
    el máximo está entre ellos 
    '' ' 
    si  abs ( derecha  -  izquierda )  <  absolutePrecision : 
        return  ( left  +  right ) / 2

    leftThird  =  ( 2 * left  +  right ) / 3 
    rightThird  =  ( left  +  2 * right ) / 3

    if  f ( leftThird )  <  f ( rightThird ): 
        return  ternarySearch ( f ,  leftThird ,  right ,  absolutePrecision )  
    else : 
        return  ternarySearch ( f ,  left ,  rightThird ,  absolutePrecision )

Algoritmo iterativo [ editar ]

def  ternarySearch ( f ,  left ,  right ,  absolutePrecision ): 
    "" " 
    Encuentre el máximo de la función unimodal f () dentro de [left, right] 
    Para encontrar el mínimo, invierta la instrucción if / else o invierta la comparación. 
    " "" 
    while  True : 
        #left y right son los límites actuales; el máximo está entre ellos 
        si  abs ( derecha  -  izquierda )  <  absolutePrecision : 
            return  ( left  +  right ) / 2

        leftThird  =  left  +  ( right  -  left ) / 3 
        rightThird  =  right  -  ( right  -  left ) / 3

        si  f ( leftThird )  <  f ( rightThird ): 
            left  =  leftThird 
        más : 
            right  =  rightThird