[I2] Dudas Calcular Mediana

[Ignaciomendezp]

Hola! Tengo un par de dudas con respecto al algoritmo de calcular mediana.

1. La notación de n^(3/4) significa realmente elevar n a 3/4 o tiene otra interpretación en este algoritmo? De ser así, ¿Cuál es la idea de calcular n^(3/4)?
2. Cómo se conectan los 2 algoritmos de la foto? Se supone que el de abajo es el MergeSort(L)? Como no tiene nombre el algoritmo de abajo me confundí.
3. Qué significan el "d" y el "u" en el algoritmo de abajo?

Muchas gracias 😅

[BFFV]

Hola!

1) Se refiere literalmente a hacer n^(3/4). La idea aquí es que este algoritmo de calcular mediana debe ser de orden lineal O(n). Cuando se hace el paso de Mergesort(R), sabemos que la complejidad de ordenar una lista de n elementos es O(n * log(n)), lo que es mayor que O(n) y por lo tanto no nos sirve. Pero si se sacan n^(3/4) elementos de la lista original, ordenar eso es O(n^(3/4) * log(n^(3/4))) = O((3/4) * n^(3/4) * log(n)) = O(n^(3/4) * log(n)), lo que sí es O(n). Por lo tanto, la razón de elevar a una fracción el n es que así se podrá ordenar esa nueva lista con menos elementos en tiempo lineal (que es necesario para que todo el algoritmo cumpla con ser O(n).

2) El algoritmo de la segunda foto es el mismo de la primera, sólo que continúa en otra slide por temas de espacio (la primera línea de la segunda foto viene justo después de la línea que dice Mergesort(R) de la primera foto).

3) El d y u representan los extremos inferior (el d) y superior (el u) de un intervalo sobre la lista R. De hecho, si te paras en la mitad de la lista R, moverse desde ahí un total de n^(1/2) entradas hacia la izquierda te deja justamente en la posición d, y moverse n^(1/2) entradas hacia la derecha te deja en la posición u. Esto se ocupa porque la idea del algoritmo es tratar de encontrar la mediana de la lista grande L dentro de este intervalo de la lista pequeña R.

[Ignaciomendezp]

Muy agradecido de la respuesta, muchas gracias! 🙌🏻 🙌🏻 🙌🏻