Dividey Venceras

Algoritmo divide y vencerás
De Wikipedia, la enciclopedia libre
Saltar a: navegación, búsqueda
En la cultura popular, divide y vencerás hace referencia a un refrán que implica resolver un problemadifícil, dividiéndolo en partes más simples tantas veces como sea necesario, hasta que la resolución de las partes se torna obvia. La solución del problema principal se construye con las solucionesencontradas.
En las ciencias de la computación, el término divide y vencerás (DYV) hace referencia a uno de los más importantes paradigmas de diseño algorítmico. El método está basado en la resoluciónrecursiva de un problema dividiéndolo en dos o más subproblemas de igual tipo o similar. El proceso continúa hasta que éstos llegan a ser lo suficientemente sencillos como para que se resuelvandirectamente. Al final, las soluciones a cada uno de los subproblemas se combinan para dar una solución al problema original.
Esta técnica es la base de los algoritmos eficientes para casi cualquier tipode problema como, por ejemplo, algoritmos de ordenamiento (quicksort, mergesort, entre muchos otros), multiplicar números grandes (Karatsuba), análisis sintácticos (análisis sintáctico top-down) y latransformada discreta de Fourier.
Por otra parte, analizar y diseñar algoritmos de DyV son tareas que lleva tiempo dominar. Al igual que en la inducción, a veces es necesario sustituir el problemaoriginal por uno más complejo para conseguir realizar la recursión, y no hay un método sistemático de generalización.
El nombre divide y vencerás también se aplica a veces a algoritmos que reducen cadaproblema a un único subproblema, como la búsqueda binaria para encontrar un elemento en una lista ordenada (o su equivalente en computación numérica, el algoritmo de bisección para búsqueda deraíces). Estos algoritmos pueden ser implementados más eficientemente que los algoritmos generales de “divide y vencerás”; en particular, si es usando una serie de recursiones que lo convierten en simples...