Algoritmos 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 $\mathrm{\Theta }(n^2)$‍. 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 $\mathrm{\Theta }(n\lg n)$‍ en todos los casos y el ordenamiento rápido se ejecuta en un tiempo $\mathrm{\Theta }(n\lg n)$‍ en el mejor caso y en el caso promedio, aunque el tiempo de ejecución de su peor caso es $\mathrm{\Theta }(n^2)$‍. Aquí hay una tabla de estos cuatro algoritmos de ordenamiento y sus tiempos de ejecución:

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:

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.