Contenido principal
Ciencias de la computación
Curso: Ciencias de la computación > Unidad 1
Lección 8: Ordenamiento por mezclaAnálisis del ordenamiento por mezcla
Dado que la función al mezclar elementos, ¿cómo llegamos a mostrar que ? Empezamos por pensar acerca de las tres partes de divide y vencerás y cómo contabilizar sus tiempos de ejecución. Suponemos que estamos ordenando un total de elementos en todo el arreglo.
merge
se ejecuta en un tiempo mergeSort
se ejecuta en un tiempo - El paso de dividir tarda un tiempo constante, sin importar el tamaño del subarreglo. Después de todo, el paso de dividir simplemente calcula el punto medio
de los índices y . Recuerda que en la notación Θ grande, indicamos un tiempo constante por . - El paso de vencer, en donde ordenamos dos subarreglos de aproximadamente
elementos cada uno, se tarda una cierta cantidad de tiempo, pero vamos a contabilizar ese tiempo cuando consideremos los subproblemas. - El paso de combinar mezcla un total de
elementos y se tarda un tiempo .
Si pensamos acerca de los pasos de dividir y combinar juntos, el tiempo de ejecución del paso de dividir es un término de orden inferior comparado con el tiempo de ejecución del paso de combinar. Así que vamos a pensar en los pasos de dividir y de combinar que juntos tardan un tiempo . Para hacer las cosas más concretas, vamos a decir que los pasos de dividir y combinar juntos tardan un tiempo para alguna constante .
Para mantener las cosas relativamente sencillas, vamos a suponer que si , entonces siempre es par, de modo que cuando tengamos que pensar en , sea un entero. (Contabilizar para el caso en que sea impar no cambia el resultado en términos de notación Θ grande). Así que podemos pensar en el tiempo de ejecución de elementos como la suma de dos veces el tiempo de ejecución de elementos (para el paso de vencer) más (para los pasos de dividir y combinar, en realidad solo para la mezcla).
mergeSort
sobre un subarreglo de mergeSort
sobre un subarreglo de Ahora tenemos que averiguar el tiempo de ejecución de dos llamadas recursivas sobre elementos. Cada una de estas dos llamadas recursivas tarda el doble del tiempo de ejecución de elementos (porque tenemos que dividir a la mitad) más para mezclar. Tenemos dos subproblemas de tamaño , y cada uno tarda un tiempo en mezclar, de modo que el tiempo total que tardamos en mezclar los subproblemas de tamaño es .
mergeSort
sobre un subarreglo de Vamos a dibujar los tiempos de mezcla en un "árbol":
Los computólogos dibujan árboles al revés de como crecen los árboles en realidad. Un árbol es un grafo sin ciclos (caminos que empiezan y acaban en el mismo lugar). La convención es llamar los vértices en un árbol sus nodos. El nodo raíz está hasta arriba; aquí, la raíz está etiquetada con el tamaño del subarreglo para el arreglo original de elementos. Debajo están los dos nodos secundarios, cada uno etiquetado para representar los tamaños de los subarreglos para los dos subproblemas de tamaño .
Cada uno de los subproblemas de tamaño ordena recursivamente los dos subarreglos de tamaño , o . Como hay dos subproblemas de tamaño , hay cuatro subproblemas de tamaño . Cada uno de estos cuatro subproblemas mezcla un total de elementos, así que el tiempo de mezcla para cada uno de los cuatro subproblemas es . Sumados sobre los cuatro subproblemas, vemos que el tiempo total de mezcla para los cuatro subproblemas de tamaño es :
¿Qué crees que pasará con los subproblemas de tamaño ? Habrá ocho de ellos, y el tiempo de mezcla para cada uno será , para un tiempo total de mezcla de :
A medida que los subproblemas se hacen más pequeños, el número de subproblemas se duplica en cada "nivel" de la recursión, pero el tiempo de mezcla se divide a la mitad. La duplicación y división a la mitad se cancelan, de modo que el tiempo total de mezcla es en cada nivel de recursión. Eventualmente, llegamos a subproblemas de tamaño 1: el caso base. Tenemos que pasar un tiempo ordenando subarreglos de tamaño 1, porque tenemos que probar si , y esta prueba toma tiempo. ¿Cuántos subarreglos de tamaño 1 hay? Como empezamos con elementos, debe haber de ellos. Como cada caso base tarda un tiempo , digamos que en conjunto, los casos base tardan un tiempo :
Ahora ya sabemos cuánto tiempo tarda la mezcla para el tamaño de cada subproblema. El tiempo total para niveles en el árbol, el tiempo total de mezcla es . Entonces ¿qué es ? Empezamos con subproblemas de tamaño y dividimos a la mitad repetidamente hasta llegar a subproblemas de tamaño 1. Vimos esta característica cuando analizamos la búsqueda binaria, y la respuesta es . Por ejemplo, si , entonces , y efectivamente, el árbol tiene cuatro niveles: . El tiempo total para . Cuando usamos notación Θ grande para describir este tiempo de ejecución, descartamos el término de orden inferior ( ) y el coeficiente constante ( ), dándonos un tiempo de ejecución de , según lo prometido.
mergeSort
es la suma de los tiempos de mezcla para todos los niveles. Si hay mergeSort
es entonces Otra cosa acerca del ordenamiento por mezcla que vale la pena destacar. Durante la mezcla, se hace una copia de todo el arreglo que se está ordenando, con una mitad en
lowHalf
y la otra mitad en highHalf
. Como copia más de un número constante de elementos en algún momento, decimos que el ordenamiento por mezcla no trabaja in situ. En contraste, tanto el ordenamiento por selección como el ordenamiento por inserción sí trabajan in situ, ya que nunca hacen una copia de más de un número constante de elementos del arreglo en cualquier momento. A los computólogos les gusta considerar si un algoritmo trabaja in situ o no, porque hay algunos sistemas en los cuales el espacio es escaso, y por lo tanto son preferibles los algoritmos in situ.Este contenido es una colaboración de los profesores de Dartmouth Computer Science Thomas Cormen y Devin Balkcom, con el equipo de contenidos de computación de Khan Academy. El contenido está bajo licencia CC-BY-NC-SA.
¿Quieres unirte a la conversación?
- Qué crees que pasará con los subproblemas de tamaño n/8 n/8n, slash, 8?(0 votos)