Hola,
Cuando se utiliza divide and conquer y el problema divide cada parte en 3 o más sub-problemas, porque el tamaño de los sub-problemas es "n/2" en realidad n/2^i , en lugar de cada sub-problema del nivel 1 ser de tamaño n/3.
En respuesta a Enzo Drago Fuentes
Re: Divide and conquer tamaño de los problemas
de Jonathan Murana -
Hola Enzo,
si entendí bien la pregunta, una cosa es el tamaño de la entrada de los subproblemas y otra la cantidad de llamados recursivos que se hacen en cada nivel.
El ejemplo que muestras llama 3 veces la función recursiva con entrada n/2, puedes ver el ejemplo de la multiplicación entera (5.5).
Si la entrada se dividiera en 3 partes (que no es el caso) sería como dices, la verdad no conozco ningún ejemplo.
Saludos
si entendí bien la pregunta, una cosa es el tamaño de la entrada de los subproblemas y otra la cantidad de llamados recursivos que se hacen en cada nivel.
El ejemplo que muestras llama 3 veces la función recursiva con entrada n/2, puedes ver el ejemplo de la multiplicación entera (5.5).
Si la entrada se dividiera en 3 partes (que no es el caso) sería como dices, la verdad no conozco ningún ejemplo.
Saludos
En respuesta a Jonathan Murana
Re: Divide and conquer tamaño de los problemas
de Enzo Drago Fuentes -
No estaba entendiendo porque se repetia el trabajo en las llamadas recursivas. Es una característica de la solución entonces.
Muchas gracias!