Me refiero al algoritmo presentado aquí utilizado para encontrar un buen pivote: http://en.wikipedia.org/wiki/Selection_algorithm#Linear_general_selection_algorithm_-_Median_of_Medians_algorithm
Mi pregunta es que no entiendo muy bien por qué los elementos tienen que estar divididos específicamente en grupos de 5. ¿Por qué no otro número?
La sección clave del artículo de Wikipedia dice
La llamada recursiva de cálculo de la mediana no supera el peor caso comportamiento lineal porque la lista de medianas es el 20% del tamaño de la lista, mientras que la otra llamada recursiva recurre como máximo al 70% de la lista, lo que hace que el tiempo de ejecución $$T(n) \leq T(n/5) + T(7 \cdot n/10) + O(n).$$
El O( $n$ ) es para el trabajo de partición (visitamos cada elemento a número constante de veces, para formarlos en $n/5$ grupos y tomar cada mediana en O( $1$ ) tiempo). A partir de esto, se puede demostrar que $$T(n) \leq c \cdot n \cdot (1 + (9/10) + (9/10)^2 + \cdots) \in O(n).$$
utilizando el hecho de que como máximo el 70% de la lista está a un lado de la mediana de las medianas con grupos de cinco.
Si en lugar de eso tuvieras grupos de tres, la primera desigualdad sería $$T(n) \leq T(n/3) + T(2 \cdot n/3) + O(n)$$ por lo que no se obtendría una serie convergente en la segunda desigualdad.
No hay ninguna razón para no utilizar algo mayor que cinco; por ejemplo, con siete la primera desigualdad sería $$T(n) \leq T(n/7) + T(5 \cdot n/7) + O(n)$$ que también funciona, pero cinco es el número impar más pequeño (útil para las medianas) que funciona.
¡Gracias por la ayuda! Pero todavía estoy un poco confundido. No veo cómo se obtiene c*n*(1 + (9/10)+(9/10)^2...) E 0(n) a partir del mencionado tiempo de ejecución.
El $c \cdot n \cdot 1$ proviene del $O(n)$ mientras que el $c \cdot n \cdot \frac{9}{10}$ El término viene de la $O(n/5) +O(7n/10)$ que aparecerá desde $\frac{n}{5}+\frac{7n}{10} = \frac{9n}{10}$ y de forma similar más abajo en la recursión.
Hola @Henry!!! ¿podrías explicarme cómo encontramos la relación de recurrencia que describe el coste del algoritmo? El algoritmo es este: math.stackexchange.com/questions/1180071/
También puede utilizar otros tamaños de bloque, como el 3 o el 4, como se muestra en el documento Seleccione con grupos de 3 o 4 por K. Chen y A. Dumitrescu (2015). La idea es utilizar el algoritmo de la "mediana de las medianas" dos veces y hacer la partición solo después. Esto disminuye la calidad del pivote pero es más rápido. En el documento lo llaman "Algoritmo de pasos repetidos".
Así que en lugar de:
T(n) <= T(n/3) + T(2n/3) + O(n)
T(n) = O(nlogn)uno recibe:
T(n) <= T(n/9) + T(7n/9) + O(n)
T(n) = Theta(n) I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
