Contenido principal
Ciencias de la computación
Curso: Ciencias de la computación > Unidad 1
Lección 8: Ordenamiento por mezclaAlgoritmos de divide y vencerás
Los dos algoritmos de ordenamiento que hemos visto hasta ahora, el ordenamiento por selección y el ordenamiento por inserción, tienen un tiempo de ejecución para el peor caso de \Theta, left parenthesis, n, squared, right parenthesis. Cuando el tamaño de la entrada del arreglo es grande, estos algoritmos pueden tardar mucho tiempo en ejecutarse. En esta lección y en la que sigue, vamos a ver otros dos algoritmos de ordenamiento: el ordenamiento por mezcla y el ordenamiento rápido, los cuales tienen mejores tiempos de ejecución. En particular, el ordenamiento por mezcla se ejecuta en un tiempo \Theta, left parenthesis, n, \lg, n, right parenthesis en todos los casos y el ordenamiento rápido se ejecuta en un tiempo \Theta, left parenthesis, n, \lg, n, right parenthesis en el mejor caso y en el caso promedio, aunque el tiempo de ejecución de su peor caso es \Theta, left parenthesis, n, squared, right parenthesis. Aquí hay una tabla de estos cuatro algoritmos de ordenamiento y sus tiempos de ejecución:
Algoritmo | Tiempo de ejecución del peor caso | Tiempo de ejecución del mejor caso | Tiempo de ejecución del caso promedio |
---|---|---|---|
ordenamiento por selección | \Theta, left parenthesis, n, squared, right parenthesis | \Theta, left parenthesis, n, squared, right parenthesis | \Theta, left parenthesis, n, squared, right parenthesis |
Ordenamiento por inserción | \Theta, left parenthesis, n, squared, right parenthesis | \Theta, left parenthesis, n, right parenthesis | \Theta, left parenthesis, n, squared, right parenthesis |
Ordenamiento por mezcla | \Theta, left parenthesis, n, \lg, n, right parenthesis | \Theta, left parenthesis, n, \lg, n, right parenthesis | \Theta, left parenthesis, n, \lg, n, right parenthesis |
Ordenamiento rápido | \Theta, left parenthesis, n, squared, right parenthesis | \Theta, left parenthesis, n, \lg, n, right parenthesis | \Theta, left parenthesis, n, \lg, n, right parenthesis |
Divide y vencerás
Tanto el ordenamiento por mezcla como el ordenamiento rápido emplean un paradigma algorítmico común que se basa en la recursividad. Este paradigma, divide y vencerás, separa un problema en subproblemas que se parecen al problema original, de manera recursiva resuelve los subproblemas y, por último, combina las soluciones de los subproblemas para resolver el problema original. Como divide y vencerás resuelve subproblemas de manera recursiva, cada subproblema debe ser más pequeño que el problema original, y debe haber un caso base para los subproblemas. Debes pensar que los algoritmos de divide y vencerás tienen tres partes:
- Divide el problema en un número de subproblemas que son instancias más pequeñas del mismo problema.
- Vence los subproblemas al resolverlos de manera recursiva. Si son los suficientemente pequeños, resuelve los subproblemas como casos base.
- Combina las soluciones de los subproblemas en la solución para el problema original.
Puedes recordar fácilmente los pasos para un algoritmo de divide y vencerás como divide, conquista, combina. Aquí está cómo ver un paso, al suponer que cada paso de dividir crea dos subproblemas (aunque algunos algoritmos de divide y vencerás crean más de dos):
Si expandimos a dos pasos recursivos más, se ve así:
Como divide y vencerás crea por lo menos dos subproblemas, un algoritmo de divide y vencerás hace muchas llamadas recursivas.
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é es un paradigma algorítmico ?, un lema o algo así. Otra cosa cuando divido un problema en subproblemas, como ó cuando se en que momento detenerme, si a cada subproblema puede ser que no encuentre una solución , si no que más bien llego a otro problema. Osea el procedimiento puede hacerse enorme.(2 votos)
- ¿como se divide los algoritmos?(2 votos)
- en el plano cartesiano se podria realizar con valores negativos(1 voto)
- ¿No entiendo como hacer el diagrama(1 voto)
- ¿Estos documentos estan siendo traducidos? o ya mejor dejo de esperar que los traduscan.(1 voto)