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

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 \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:
AlgoritmoTiempo de ejecución del peor casoTiempo de ejecución del mejor casoTiempo 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:
  1. Divide el problema en un número de subproblemas que son instancias más pequeñas del mismo problema.
  2. Vence los subproblemas al resolverlos de manera recursiva. Si son los suficientemente pequeños, resuelve los subproblemas como casos base.
  3. 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?

  • Avatar male robot hal style para el usuario William Azuaje
    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)
    Avatar Default Khan Academy avatar para el usuario
  • Avatar blobby green style para el usuario miyukiWTF
    ¿como se divide los algoritmos?
    (2 votos)
    Avatar Default Khan Academy avatar para el usuario
  • Avatar blobby green style para el usuario Jess Mena
    en el plano cartesiano se podria realizar con valores negativos
    (1 voto)
    Avatar Default Khan Academy avatar para el usuario
  • Avatar blobby green style para el usuario isabellacargar
    ¿No entiendo como hacer el diagrama
    (1 voto)
    Avatar Default Khan Academy avatar para el usuario
  • Avatar male robot hal style para el usuario Sergio Yañez
    ¿Estos documentos estan siendo traducidos? o ya mejor dejo de esperar que los traduscan.
    (1 voto)
    Avatar Default Khan Academy avatar para el usuario
¿Sabes inglés? Haz clic aquí para ver más discusiones en el sitio en inglés de Khan Academy.