Open zusmoshijiku opened 8 months ago
zusmoshijiku
commented
8 months ago Ahora entendí que se trata de los T's de las líneas 6, 7 y 8 (p = floor(n/3), q - p = floor(n/3) y n-q = ceil(n/3)) (creo). De todas formas agradecería una explicación más rigurosa.
ibgarrido
commented
8 months ago Respondiendo a tu pregunta de por que calza el teorema maestro en este problema:
El teorema maestro es utilizado para resolver ecuaciones de recurrencias que puedes definir para un algoritmo recursivo basado en la estrategia dividir para conquistar en ordenamiento (Es decir, cuando recursivamente, dividimos, por ejemplo, un arreglo de numeros en subarreglos mas chicos). Como debiste ver en clases, Merge Sort usa dicha estrategia para ordenar datos, por lo que no es raro pensar que esta variante llamada 'Triple Merge Sort' haga lo mismo, asi que el desafio que tenemos es definir una ecuacion de recurrencia buena para TripleMergeSort:
Si el arreglo tiene largo Cardinal(A) = n, entonces al dividir el arreglo en 3 fragmentos, tenemos que el intervalo inicial es dividido en: Primer llamado (1): A[0, [n]/3]-1] U A[[n]/3], 2[n]/3]-1] U A[2[n]/3], n-1] = A Y en general cada uno de esos subfragmentos que componen A, se van a subdivir con la misma logica debido a la recurrencia (En ese caso reemplazas n por el largo del subproblema). Una vez comprendido eso podemos armar la ecuacion de recurrencia:
Asumamos que queremos inicialmente ordenar el arreglo en orden creciente, nuestro peor caso es que este ordenado de forma decreciente y que ademas todos los valores sean distintos entre si, luego, tendriamos que hacer al menos n-1 pasos.
En este caso, como bien mencionas sobre las lineas 6,7 y 8, cada una esas recurrencias realizan a lo mas :
Linea 6:p = floor(n/3). llamados -> T(floor(n/3)) linea 7q - p = floor(n/3) llamados -> T(floor(n/3)) linea 8 n-q = ceil(n/3)) llamados -> T(ceil(n/3)) linea 9: demas n llamados de triple combinar (Ya que floor(n/3) + floor(n/3) + ceil(n/3)) = n, ya que en cada una de esas subdivisiones tambien se ejecuta una sola vez triple combinar en el return).
Luego nuestra ecuacion de recurrencia es:
T(n): {1 SI n <2 ; {2T(floor(n/3))+T(ceil(n/3))+n ; SI n>=2
Luego, aplicando el teorema maestro, como pudiste apreciar en tu resultado, se cumple que es de complejidad O(n log(n))
PD: SI quieres profundizar un poco mas eso, te dejo este link, mira la desde la pagina 29 en adelante: https://github.com/IIC2133-PUC/2023-2/blob/master/Clases/seccion2/class03.pdf
Hola, mi duda surge a partir de una pregunta de la I2-2022-2:
Con la siguiente solución:
¿Qué diferencia hay con utilizar alguna de estas otras ecuaciones de recurrencia?
Al final, el teorema maestro calza para esta pregunta en particular, pero no sé si hay algún caso en el que no sea así.