Características

horusart

 

Recursión
Los algoritmos de “divide y vencerás” están naturalmente implementados, como procesos recursivos. En ese caso, los subproblemas parciales encabezados por aquel que ya ha sido resuelto se almacenan en la pila de llamadas de procedimientos.

Pila explícita
Los algoritmos de divide y vencerás también pueden ser implementados por un programa no recursivo que almacena los subproblemas parciales en alguna estructura de datos explícita, tales como una pila, una cola, o una cola de prioridad. Este enfoque permite más libertad a la hora de elegir los subproblemas a resolver después, una característica que es importante en algunas aplicaciones, por ejemplo en la búsqueda en anchura y en el método de ramificación y poda para optimización de subproblemas. Este enfoque es también la solución estándar en lenguajes de programación que no permiten procedimientos recursivos.

Tamaño de la pila
En implementaciones recursivas de algoritmos de DyV, debe asegurarse que hay suficiente memoria libre para la pila de recursión, sino la ejecución puede fallar por desbordamiento de la pila. Afortunadamente, los algoritmos DyV que son eficientes temporalmente tienen una profundidad recursiva relativamente pequeña. Por ejemplo, el algoritmo quicksort puede ser implementado de forma que nunca requiere más de log_2n llamadas recursivas para ordenar n elementos.

Los desbordamientos de pila podrían ser difíciles de evitar cuando usamos procedimientos recursivos, donde muchos compiladores asumen que la pila de recursión es una zona contigua de memoria, y algunos asignan una cantidad de espacio determinada para ello. Los compiladores pueden también asignar más información en la pila de recursión que la estrictamente necesaria, tales como la dirección de retorno, parámetros invariables, y las variables internas del procedimiento. Así, el riesgo de desbordamiento de pila puede ser reducido mediante la minimización de parámetros y variables internas de los procedimientos recursivos, o usando estructura de pila explícita.

Eligiendo los casos base
En cualquier algoritmo recursivo, hay una libertad considerable para elegir los casos bases, los subproblemas pequeños que son resueltos directamente para acabar con la recursión.

Elegir los casos base más pequeños y simples posibles es más elegante y normalmente nos da lugar a programas más simples, porque hay menos casos a considerar y son más fáciles de resolver. Por ejemplo, un algoritmo FFT podría parar la recursión cuando la entrada es una muestra simple, y el algoritmo quicksort de ordenación podría parar cuando la entrada es una lista vacía. En ambos casos, sólo hay que considerar un caso base, y no requiere procesamiento.

Por otra parte, la eficiencia normalmente mejora si la recursión se para en casos relativamente grandes, y estos son resueltos no recursivamente. Esta estrategia evita la sobrecarga de llamadas recursivas que hacen poco o ningún trabajo, y pueden también permitir el uso de algoritmos especializados no recursivos que, para esos casos base, son más eficientes que la recursión explícita. Ya que un algoritmo de DyV reduce cada instancia del problema o subproblema a un gran número de instancias base, éstas habitualmente dominan el coste general del algoritmo, especialmente cuando la sobrecarga de separación/unión es baja. Véase que estas consideraciones no dependen de si la recursión está implementada por compilador o por pila explícita.

Compartir subproblemas repetidos
Para algunos problemas, la recursión ramificada podría acabar evaluando el mismo subproblema muchas veces. En tales casos valdría la pena identificar y guardar las soluciones de estos subproblemas solapados, una técnica comúnmente conocida como memoización. Llevado al límite, nos lleva a algoritmos de “divide y vencerás” de bottom-up tales como la programación dinámica y análisis gráfico.EDF

 

Fuente:
Colaboradores de Wikipedia. Algoritmo divide y vencerás [en línea]. Wikipedia, La enciclopedia libre. Disponible en <https://es.wikipedia.org/w/index.php?title=Algoritmo_divide_y_vencer>.