If you're seeing this message, it means we're having trouble loading external resources on our website.

Si estás detrás de un filtro de páginas web, por favor asegúrate de que los dominios *.kastatic.org y *.kasandbox.org estén desbloqueados.

Contenido principal

Curso: Ciencias de la computación > Unidad 1

Lección 8: Ordenamiento por mezcla
Computación
Ciencias de la computación
Algoritmos
Ordenamiento por mezcla
© 2024 Khan AcademyTérminos de usoPolítica de privacidadAviso de cookies

Análisis del ordenamiento por mezcla

Google Classroom
Dado que la función merge se ejecuta en un tiempo Θ(n) al mezclar n elementos, ¿cómo llegamos a mostrar que mergeSort se ejecuta en un tiempo Θ(nlog2⁡n)? 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 n elementos en todo el arreglo.
  1. 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 q de los índices p y r. Recuerda que en la notación Θ grande, indicamos un tiempo constante por Θ(1).
  2. El paso de vencer, en donde ordenamos dos subarreglos de aproximadamente n/2 elementos cada uno, se tarda una cierta cantidad de tiempo, pero vamos a contabilizar ese tiempo cuando consideremos los subproblemas.
  3. El paso de combinar mezcla un total de n elementos y se tarda un tiempo Θ(n).
Si pensamos acerca de los pasos de dividir y combinar juntos, el tiempo de ejecución Θ(1) del paso de dividir es un término de orden inferior comparado con el tiempo de ejecución Θ(n) del paso de combinar. Así que vamos a pensar en los pasos de dividir y de combinar que juntos tardan un tiempo Θ(n). Para hacer las cosas más concretas, vamos a decir que los pasos de dividir y combinar juntos tardan un tiempo cn para alguna constante c.
Para mantener las cosas relativamente sencillas, vamos a suponer que si n>1, entonces n siempre es par, de modo que cuando tengamos que pensar en n/2, sea un entero. (Contabilizar para el caso en que n sea impar no cambia el resultado en términos de notación Θ grande). Así que podemos pensar en el tiempo de ejecución de mergeSort sobre un subarreglo de n elementos como la suma de dos veces el tiempo de ejecución de mergeSort sobre un subarreglo de (n/2) elementos (para el paso de vencer) más cn (para los pasos de dividir y combinar, en realidad solo para la mezcla).
Ahora tenemos que averiguar el tiempo de ejecución de dos llamadas recursivas sobre n/2 elementos. Cada una de estas dos llamadas recursivas tarda el doble del tiempo de ejecución de mergeSort sobre un subarreglo de (n/4) elementos (porque tenemos que dividir n/2 a la mitad) más cn/2 para mezclar. Tenemos dos subproblemas de tamaño n/2, y cada uno tarda un tiempo cn/2 en mezclar, de modo que el tiempo total que tardamos en mezclar los subproblemas de tamaño n/2 es 2⋅cn/2=cn.
Vamos a dibujar los tiempos de mezcla en un "árbol":
Un diagrama con un árbol a la izquierda y tiempos de mezcla a la derecha. El árbol está etiquetado como "Tamaño del subproblema" y la derecha está etiquetada como "Tiempo total de mezcla para todos los subproblemas de este tamaño". El primer nivel del árbol muestra un solo nodo n y el tiempo correspondiente de mezcla de c por n. El segundo nivel del árbol muestra dos nodos, cada uno de 1/2 n, y un tiempo de mezcla de 2 por c por 1/2 n, que es lo mismo que c por n.
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 n del subarreglo para el arreglo original de n elementos. Debajo están los dos nodos secundarios, cada uno etiquetado n/2 para representar los tamaños de los subarreglos para los dos subproblemas de tamaño n/2.
Cada uno de los subproblemas de tamaño n/2 ordena recursivamente los dos subarreglos de tamaño (n/2)/2, o n/4. Como hay dos subproblemas de tamaño n/2, hay cuatro subproblemas de tamaño n/4. Cada uno de estos cuatro subproblemas mezcla un total de n/4 elementos, así que el tiempo de mezcla para cada uno de los cuatro subproblemas es cn/4. Sumados sobre los cuatro subproblemas, vemos que el tiempo total de mezcla para los cuatro subproblemas de tamaño n/4 es 4⋅cn/4=cn:
Un diagrama con un árbol a la izquierda y tiempos de mezcla a la derecha. El árbol está etiquetado como "Tamaño del subproblema" y la derecha está etiquetada como "Tiempo total de mezcla para todos los subproblemas de este tamaño". El primer nivel del árbol muestra un solo nodo n y el tiempo correspondiente de mezcla de c por n. El segundo nivel del árbol muestra dos nodos, cada uno de 1/2 n, y un tiempo de mezcla de 2 por c por 1/2 n, que es lo mismo que c por n. El tercer nivel del árbol muestra cuatro nodos, cada uno de 1/4 n, y un tiempo de mezcla de 4 por c por 1/4 n, que es lo mismo que c por n.
¿Qué crees que pasará con los subproblemas de tamaño n/8? Habrá ocho de ellos, y el tiempo de mezcla para cada uno será cn/8, para un tiempo total de mezcla de 8⋅cn/8=cn:
Un diagrama con un árbol a la izquierda y tiempos de mezcla a la derecha. El árbol está etiquetado como "Tamaño del subproblema" y la derecha está etiquetada como "Tiempo total de mezcla para todos los subproblemas de este tamaño". El primer nivel del árbol muestra un solo nodo n y el tiempo correspondiente de mezcla de c por n. El segundo nivel del árbol muestra dos nodos, cada uno de 1/2 n, y un tiempo de mezcla de 2 por c por 1/2 n, que es lo mismo que c por n. El tercer nivel del árbol muestra cuatro nodos, cada uno de 1/4 n, y a tiempo de mezcla de 4 por c por 1/4 n, que es lo mismo que c por n. El cuarto nivel del árbol muestra ocho nodos, cada uno de 1/8 n, y un tiempo de mezcla de 8 por c por 1/8 n, que es lo mismo que c por n.
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 cn en cada nivel de recursión. Eventualmente, llegamos a subproblemas de tamaño 1: el caso base. Tenemos que pasar un tiempo Θ(1) ordenando subarreglos de tamaño 1, porque tenemos que probar si p<r, y esta prueba toma tiempo. ¿Cuántos subarreglos de tamaño 1 hay? Como empezamos con n elementos, debe haber n de ellos. Como cada caso base tarda un tiempo Θ(1), digamos que en conjunto, los casos base tardan un tiempo cn:
Un diagrama con un árbol a la izquierda y tiempos de mezcla a la derecha. El árbol está etiquetado como "Tamaño del subproblema" y la derecha está etiquetada como "Tiempo total de fusión para todos los subproblemas de este tamaño". El primer nivel del árbol muestra un solo nodo n y el tiempo correspondiente de mezcla de c por n. El segundo nivel del árbol muestra dos nodos, cada uno de 1/2 n, y un tiempo de mezcla de 2 por c por 1/2 n, que es lo mismo que c por n. El tercer nivel del árbol muestra cuatro nodos, cada uno de 1/4 n, y a tiempo de mezcla de 4 por c por 1/4 n, que es lo mismo que c por n. El cuarto nivel del árbol muestra ocho nodos, cada uno de 1/8 n, y un tiempo de mezcla de 8 por c por 1/8 n, que es lo mismo que c por n. Debajo de ese nivel, se muestran puntos para indicar que el árbol continúa de esa manera. Se muestra un nivel final con n nodos de 1 y un tiempo de mezcla de n por c, que es lo mismo que c por n.
Ahora ya sabemos cuánto tiempo tarda la mezcla para el tamaño de cada subproblema. El tiempo total para mergeSort es la suma de los tiempos de mezcla para todos los niveles. Si hay l niveles en el árbol, el tiempo total de mezcla es l⋅cn. Entonces ¿qué es l? Empezamos con subproblemas de tamaño n 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 l=log2⁡n+1. Por ejemplo, si n=8, entonces log2⁡n+1=4, y efectivamente, el árbol tiene cuatro niveles: n=8,4,2,1. El tiempo total para mergeSort es entonces cn(log2⁡n+1). Cuando usamos notación Θ grande para describir este tiempo de ejecución, descartamos el término de orden inferior (+1) y el coeficiente constante (c), dándonos un tiempo de ejecución de Θ(nlog2⁡n), según lo prometido.
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?

Inicia sesión
¿Sabes inglés? Haz clic aquí para ver más discusiones en el sitio en inglés de Khan Academy.