Me pregunto si la técnica de dividir y conquistar siempre divide un problema en subproblemas del mismo tipo? Por el mismo tipo, quiero decir que uno puede implementarlo usando una función con recursión. ¿Puede dividirse y conquistar siempre ser implementado por recursión?dividir y conquistar y recursión
Gracias!
"Siempre" es una palabra aterradora, pero no puedo pensar en una situación de dividir y vencer en la que no puedas usar recursividad. Es por definición que divide y vencerás crea subproblemas de la misma forma que el problema inicial: estos subproblemas se desglosan continuamente hasta que se alcanza un caso base y el número de divisiones se correlaciona con el tamaño de la entrada. La recursión es una elección natural para este tipo de problema.
Consulte el Wikipedia article para obtener más información.
Un algoritmo de división y conquista es, por definición, uno que se puede resolver por recursión. Entonces la respuesta es sí.
¡Normalmente, sí! Merge sort es un ejemplo de lo mismo. Aquí hay un animated version de lo mismo.
Sí. En la técnica algorítmica de dividir y conquistar, dividimos el problema más grande dado en sub-problemas más pequeños. Estos sub-problemas más pequeños deben ser similares al problema más grande, excepto que son de menor tamaño.
Por ejemplo, el problema de ordenar una matriz de tamaño N no es diferente del problema de ordenar una matriz de tamaño N/2. Excepto que el último tamaño del problema es más pequeño que el anterior.
Si el sub-problema más pequeño no es similar al más grande, entonces la técnica de dividir y conquistar no se puede usar para resolver el problema más grande. En otras palabras, un problema determinado puede resolverse utilizando la técnica de dividir y conquistar solo si el problema más grande dado se puede dividir en subproblemas más pequeños que son similares al problema más grande.
La recursividad es un método de programación en el que se define una función en términos de sí misma. La función generalmente se llama a sí misma con parámetros levemente modificados (para converger).
Examinar el algoritmo de ordenación por fusión será suficiente para esta pregunta. Después de comprender la implementación del algoritmo de ordenación por fusión con divide y vencerás (también recurrencia) verás lo difícil que sería hacerlo sin recurrencia.
En realidad, lo más importante aquí es la complejidad del algoritmo que se expresa con la notación big-oh y nlogn para ordenar por fusión.
Para mergesort exapmle hay otra versión que se llama tipo de fusión de abajo arriba. Es una versión simple y no recursiva de la misma.
es aproximadamente un 10% más lento que recurrente, de arriba hacia abajo mergesort en sistemas típicos. Puede consultar el siguiente enlace para más información. Se explica bien en la tercera conferencia.