En informática , la mediana de medianas es un algoritmo aproximado de selección de medianas , que se utiliza con frecuencia para proporcionar un buen pivote para un algoritmo de selección exacto, más comúnmente quickselect , que selecciona el k -ésimo elemento más pequeño de una matriz inicialmente no ordenada. La mediana de medianas encuentra una mediana aproximada en tiempo lineal. Al utilizar esta mediana aproximada como un pivote mejorado, la complejidad del peor de los casos de quickselect se reduce de cuadrática a lineal , que también es la complejidad del peor de los casos asintóticamente óptima de cualquier algoritmo de selección. En otras palabras, la mediana de medianas es un algoritmo aproximado de selección de medianas que ayuda a construir un algoritmo de selección general exacto y asintóticamente óptimo (especialmente en el sentido de complejidad del peor de los casos), al producir buenos elementos pivote.
La mediana de medianas también se puede utilizar como una estrategia de pivote en quicksort , produciendo un algoritmo óptimo, con la complejidad del peor caso . [ cita requerida ] Aunque este enfoque optimiza bastante bien la complejidad asintótica del peor caso, generalmente se supera en la práctica al elegir pivotes aleatorios por su complejidad promedio para la selección y la complejidad promedio para la clasificación, sin ninguna sobrecarga de cálculo del pivote.
De manera similar, la mediana de medianas se utiliza en el algoritmo de introselect híbrido como una alternativa para la selección de pivotes en cada iteración hasta que se encuentra el k-ésimo más pequeño. Esto nuevamente garantiza un rendimiento lineal en el peor de los casos, además del rendimiento lineal en el caso promedio: la introselect comienza con una selección rápida (con pivote aleatorio, predeterminado), para obtener un buen rendimiento promedio, y luego vuelve a una selección rápida modificada con pivote obtenido a partir de la mediana de medianas si el progreso es demasiado lento. Aunque asintóticamente similar, un algoritmo híbrido de este tipo tendrá una complejidad menor que una introselect sencilla hasta un factor constante (tanto en el caso promedio como en el peor de los casos), en cualquier longitud finita.
El algoritmo fue publicado en Blum et al. (1973), y por eso a veces se lo llama BFPRT por los apellidos de los autores. En el artículo original, el algoritmo se denominaba PICK y se hacía referencia a la selección rápida como "FIND".
Quickselect es lineal en promedio, pero puede requerir tiempo cuadrático con malas elecciones de pivote. Esto se debe a que quickselect es un algoritmo de divide y vencerás , en el que cada paso toma tiempo en el tamaño del conjunto de búsqueda restante. Si el conjunto de búsqueda disminuye exponencialmente rápido en tamaño (en una proporción fija), esto produce una serie geométrica multiplicada por el factor de un solo paso y, por lo tanto, un tiempo general lineal. Sin embargo, si el conjunto de búsqueda disminuye lentamente en tamaño, como linealmente (en una cantidad fija de elementos, en el peor de los casos solo se reduce en un elemento cada vez), entonces una suma lineal de pasos lineales produce un tiempo general cuadrático (formalmente, los números triangulares crecen cuadráticamente). Por ejemplo, el peor de los casos ocurre cuando se pivotea sobre el elemento más pequeño en cada paso, como al aplicar quickselect para el elemento máximo a datos ya ordenados y tomar el primer elemento como pivote cada vez.
Si, en cambio, se eligen sistemáticamente pivotes "buenos", esto se evita y siempre se obtiene un rendimiento lineal incluso en el peor de los casos. Un pivote "bueno" es aquel para el que podemos establecer que una proporción constante de elementos cae tanto por debajo como por encima de él, ya que entonces el conjunto de búsqueda disminuye al menos en una proporción constante en cada paso, por lo tanto exponencialmente rápido, y el tiempo total sigue siendo lineal. La mediana es un buen pivote (el mejor para ordenar y la mejor opción general para la selección), ya que reduce el conjunto de búsqueda a la mitad en cada paso. Por lo tanto, si se puede calcular la mediana en tiempo lineal, esto solo agrega tiempo lineal a cada paso y, por lo tanto, la complejidad general del algoritmo sigue siendo lineal.
El algoritmo de mediana de medianas calcula una mediana aproximada, es decir, un punto que se garantiza que se encuentra entre los percentiles 30 y 70 (en los 4 deciles intermedios ). De este modo, el conjunto de búsqueda disminuye al menos un 30 %. El problema se reduce al 70 % del tamaño original, que es una proporción fija más pequeña. La aplicación del mismo algoritmo en el conjunto ahora más pequeño de forma recursiva hasta que solo queden uno o dos elementos da como resultado un costo de
Como se indicó anteriormente, la mediana de medianas se utiliza como una estrategia de selección de pivote en el algoritmo de selección rápida , que en pseudocódigo se ve de la siguiente manera.
función nthSmallest(lista, n) índice := select(lista, 1, longitud de la lista, n) // Use select(lista, 0, longitud de la lista - 1, n - 1) si la lista tiene numeración basada en cero return list[index]
Tenga cuidado al manejar lefty al implementar. El siguiente pseudocódigo supone que , y la lista usan numeración basada en uno y que se llama inicialmente con 1 como argumento y la longitud rightde la lista como argumento . Tenga en cuenta que esto devuelve el índice del n-ésimo número más pequeño después de reorganizar la lista, en lugar del valor real del n-ésimo número más pequeño.nleftrightselectleftright
función select(lista, izquierda, derecha, n) bucle si izquierda = derecha entonces retorna izquierda pivotIndex := pivot(lista, izquierda, derecha) pivotIndex := partición(lista, izquierda, derecha, pivotIndex, n) si n = pivotIndex entonces devuelve n de lo contrario si n < pivotIndex entonces derecha := pivotIndex - 1 demás izquierda := pivotIndex + 1
La subrutina pivot es el algoritmo de mediana de medianas real. Divide su entrada (una lista de longitud n ) en grupos de cinco elementos como máximo, calcula la mediana de cada uno de esos grupos utilizando alguna subrutina y luego calcula de manera recursiva la mediana verdadera de las medianas encontradas en el paso anterior:. [1] Tenga en cuenta que pivot llama a select ; esta es una instancia de recursión mutua .
función pivot(lista, izquierda, derecha) // para 5 o menos elementos solo obtiene la mediana si derecha − izquierda < 5 entonces retorna partición5(lista, izquierda, derecha) // de lo contrario mueve las medianas de los subgrupos de cinco elementos a las primeras n/5 posiciones para i de izquierda a derecha en pasos de 5 // obtiene la posición mediana del i-ésimo subgrupo de cinco elementos subDerecha := i + 4 si subDerecha > derecha entonces subDerecha := derecha mediana5 := partición5(lista, i, subDerecha) Intercambiar lista[mediana5] y lista[izquierda + piso((i − izquierda) / 5)] // Calcular la mediana de las n/5 medianas de cinco medio := piso((derecha − izquierda) / 10) + izquierda + 1 devuelve select(lista, izquierda, izquierda + piso((derecha − izquierda) / 5), medio)
Existe una subrutina llamada partición que puede, en tiempo lineal, agrupar una lista (que va desde los índices hasta ) en tres partes, las menores que un elemento determinado, las iguales a él y las mayores que el elemento ( una partición de tres vías ). La agrupación en tres partes garantiza que la mediana de las medianas mantenga un tiempo de ejecución lineal en el caso de que muchos o todos los elementos coincidan. A continuación se muestra un pseudocódigo que realiza una partición sobre el elemento :leftrightlist[pivotIndex]
función partición(lista, izquierda, derecha, pivotIndex, n) valorPivot := lista[índicePivot] Intercambiar lista[pivotIndex] y lista[right] // Mover el pivote al final storeIndex := izquierda // Mueve todos los elementos más pequeños que el pivote a la izquierda del pivote para i de izquierda a derecha − 1 do if list[i] < pivotValue then Intercambiar lista[storeIndex] y lista[i] Incrementar índice de tienda // Mueve todos los elementos iguales al pivote justo después de los elementos más pequeños storeIndexEq := índice de tienda para i desde storeIndex hasta la derecha − 1 hacer si list[i] = pivotValue entonces Intercambiar lista[storeIndexEq] y lista[i] incrementar storeIndexEq swap list[right] y list[storeIndexEq] // Mueve el pivote a su lugar final // Devuelve la ubicación del pivote considerando la ubicación deseada n si n < storeIndex entonces devuelve storeIndex // n está en el grupo de elementos más pequeños si n ≤ storeIndexEq entonces devuelve n // n está en el grupo igual al pivote devuelve storeIndexEq // n está en el grupo de elementos más grandes
La subrutina partición5 selecciona la mediana de un grupo de cinco elementos como máximo; una forma sencilla de implementar esto es la ordenación por inserción , como se muestra a continuación. [1] También se puede implementar como un árbol de decisiones .
función partición5(lista, izquierda, derecha) yo := izquierda + 1 mientras yo ≤ correcto hago yo mientras j > izquierda y lista[j−1] > lista[j] hacen Intercambiar lista[j−1] y lista[j] j := j − 1 yo := yo + 1 volver izquierda + (derecha - izquierda) / 2
De los grupos, la mitad de los grupos tienen su mediana menor que el pivote (Mediana de Medianas). Además, otra mitad de los grupos tienen su mediana mayor que el pivote. En cada uno de los grupos con mediana menor que el pivote, hay dos elementos que son menores que sus respectivas medianas, que son menores que el pivote. Por lo tanto, cada uno de los grupos tiene al menos 3 elementos que son menores que el pivote. De manera similar, en cada uno de los grupos con mediana mayor que el pivote, hay dos elementos que son mayores que sus respectivas medianas, que son mayores que el pivote. Por lo tanto, cada uno de los grupos tiene al menos 3 elementos que son mayores que el pivote. Por lo tanto, el pivote es menor que elementos y mayor que otros elementos. Por lo tanto, la mediana elegida divide los elementos ordenados en algún lugar entre 30%/70% y 70%/30%, lo que asegura un comportamiento lineal en el peor de los casos del algoritmo. Para visualizar:
(rojo = "(una de las dos posibles) mediana de medianas", gris = "número < rojo", blanco = "número > rojo")
Aquí se muestran las 5-tuplas ordenadas por mediana para mayor claridad. No es necesario ordenar las tuplas porque solo necesitamos la mediana para usarla como elemento pivote.
Tenga en cuenta que todos los elementos arriba/a la izquierda del rojo (30% de los 100 elementos) son menores, y todos los elementos abajo/a la derecha del rojo (otro 30% de los 100 elementos) son mayores.
La llamada recursiva que calcula la mediana no excede el comportamiento lineal del peor caso porque la lista de medianas tiene un tamaño de , mientras que la otra llamada recursiva recurre como máximo en el 70 % de la lista. Sea , el tiempo que lleva ejecutar un algoritmo de selección rápida de medianas en una matriz de tamaño . Entonces sabemos que este tiempo es:
dónde
Por inducción:
El paso clave es reducir el problema a la selección de dos listas cuya longitud total sea menor que la lista original, más un factor lineal para el paso de reducción. Esto permite una inducción simple para demostrar que el tiempo total de ejecución es lineal.
La elección específica de grupos de cinco elementos se explica de la siguiente manera. En primer lugar, calcular la mediana de una lista impar es más rápido y más simple; si bien se podría usar una lista par, esto requiere tomar el promedio de los dos elementos del medio, lo que es más lento que simplemente seleccionar el único elemento exacto del medio. En segundo lugar, cinco es el número impar más pequeño tal que la mediana de las medianas funciona. Con grupos de solo tres elementos, la lista resultante de medianas para buscar es length , y reduce la lista a recursivamente en length , ya que es mayor que 1/2 × 2/3 = 1/3 de los elementos y menor que 1/2 × 2/3 = 1/3 de los elementos. Por lo tanto, esto todavía deja elementos para buscar, lo que no reduce el problema lo suficiente. Sin embargo, las listas individuales son más cortas y se puede limitar la complejidad resultante a mediante el método de Akra-Bazzi , pero no prueba la linealidad.
Por el contrario, se puede agrupar por = siete, nueve o más elementos, y esto funciona. Esto reduce el tamaño de la lista de medianas a , y el tamaño de la lista para recursivamente en asíntotas en 3 n /4 (75%), ya que los cuadrantes en la tabla anterior se aproximan al 25%, ya que el tamaño de las líneas superpuestas disminuye proporcionalmente. Esto reduce el factor de escala de 10 asintóticamente a 4, pero en consecuencia aumenta el término para el trabajo de partición. Encontrar la mediana de un grupo más grande lleva más tiempo, pero es un factor constante (que depende solo de ), y por lo tanto no cambia el rendimiento general a medida que n crece. De hecho, considerando el número de comparaciones en el peor de los casos, el factor constante es .
Si, en cambio, se agrupa de la otra manera, por ejemplo, dividiendo la lista de elementos en 5 listas, calculando la mediana de cada una y luego calculando la mediana de estas (es decir, agrupando por una fracción constante, no por un número constante), no se reduce tan claramente el problema, ya que requiere calcular 5 medianas, cada una en una lista de elementos, y luego recurrir a una lista de longitud como máximo . Al igual que con la agrupación por 3, las listas individuales son más cortas, pero la longitud total no es más corta (de hecho, es más larga) y, por lo tanto, solo se pueden demostrar límites superlineales. Agrupar en un cuadrado listas de longitud es igualmente complicado.
