Si las versiones iterativas y recursivas de dos algoritmos tienen la misma complejidad? Digamos, por ejemplo, las versiones iterativas y recursivas de la serie de Fibonacci.¿La versión iterativa y recursiva tiene la misma complejidad?
La respuesta depende en gran medida de su implementación. Para el ejemplo que brindó hay varias soluciones posibles y yo diría que la forma ingenua de implementar una solución tiene una mayor complejidad cuando se implementa iterativa. Éstos son los dos implementaciones:
int iterative_fib(int n) {
if (n <= 2) {
return 1;
}
int a = 1, b = 1, c;
for (int i = 0; i < n - 2; ++i) {
c = a + b;
b = a;
a = c;
}
return a;
}
int recursive_fib(int n) {
if (n <= 2) {
return 1;
}
return recursive_fib(n - 1) + recursive_fib(n-2);
}
En ambas implementaciones asumí una entrada correcta es decir n> = 1. El primer código es mucho más largo pero su complejidad es O (n), es decir lineal, mientras que la segunda aplicación es más corto pero tiene una complejidad exponencial O (fib (n)) = O (φ^n) (φ = (1+√5)/2) y, por lo tanto, es mucho más lenta. Se puede mejorar la versión recursiva introduciendo la memorización (es decir, recordando los valores devueltos de la función que ya ha calculado). Esto generalmente se hace al introducir una matriz donde almacena los valores. Aquí está un ejemplo:
int mem[1000]; // initialize this array with some invalid value. Usually 0 or -1
// as memset can be used for that: memset(mem, -1, sizeof(mem));
int mem_fib(int n) {
if (n <= 2) {
return mem[n] = 1;
}
if (mem[n-1] == -1) {
solve(n-1);
}
if (mem[n-2] == -1) {
solve(n-2);
}
return mem[n] = mem[n-1] + mem[n-2];
}
aquí la complejidad del algoritmo recursivo es lineal al igual que la solución iterativa. La solución que presenté anteriormente es el enfoque de arriba hacia abajo para la solución de programación dinámica de su problema. El enfoque ascendente conducirá a algo muy similar a la solución que introduje como iterativo. Hay una gran cantidad de artículos sobre la programación dinámica incluidos en wikipedia
En función de los problemas que he conocido en mi experiencia algunos son mucho más difícil que hay que resolver con el enfoque de abajo hacia arriba (es decir, solución iterativa), mientras que otros son difíciles de resolver con un enfoque de arriba hacia abajo. Sin embargo, la teoría establece que cada problema que tiene una solución iterativa tiene un recursivo con la misma complejidad computacional (y viceversa).
Espero que ayude esta respuesta.
nota: no es necesario comprobar 'mem [n-2]'. –
'Diría que la forma ingenua de implementar una solución tiene una mayor complejidad cuando se implementa iterativa. Diría que la versión iterativa ya no es ingenua. El problema con la secuencia de Fibonacci es que es terriblemente fácil escribir una versión recursiva exponencial, pero escribir una versión iterativa exponencial es difícil, por lo que la primera versión que se presenta al escribir un algoritmo iterativo no es realmente ingenua, debes haber invertido un poco de pensamiento para llegar a cualquier iteración en absoluto. –
Sí, si utiliza exactamente las mismas ideas que subyacen al algoritmo, no importa. Sin embargo, la recursión es a menudo fácil de usar con respecto a la iteración. Por ejemplo, escribir una versión recursiva de las torres de Hanoi es bastante fácil. La transformación de la versión recursiva en una versión iterativa correspondiente es difícil y propensa a errores, aunque puede hacerse. En realidad, existe un teorema que establece que cada algoritmo recursivo puede transformarse en uno iterativo equivalente (para ello, se requiere imitar iterativamente la recursión utilizando una o más estructuras de datos de la pila para mantener parámetros pasados a invocaciones recursivas).
Si toma algún algoritmo recursivo, puede convertirlo en iterativo almacenando todas las variables locales de la función en una matriz, simulando de manera efectiva la pila en el montón. Si se hace así, no hay diferencia entre iterativo y recursivo.
Tenga en cuenta que hay (al menos) dos algoritmos de Fibonacci recursivos, por lo que para el ejemplo para ser exactos necesita especificar de qué algoritmo recursivo está hablando.
Sí, cada algoritmo iterativo puede transformarse en versión recursiva y viceversa. Una forma de pasar las continuaciones y la otra implementando la estructura de la pila. Esto se hace sin aumentar la complejidad del tiempo.
Si puede optimizar la recursividad de la cola, entonces cada algoritmo iterativo se puede transformar en recursivo sin aumentar la complejidad de la memoria asintótica.
El algoritmo recursivo particular para el cálculo de la serie fibanocci es menos eficiente. considere la siguiente situación de encontrar fib (4) a través del algoritmo recursivo
int fib(n) :
if(n==0 || n==1)
return n;
else
return fib(n-1) + fib(n-2)
Ahora, cuando el algoritmo anterior se ejecuta para n = 4
fib(4)
fib(3) fib(2)
fib(2) fib(1) fib(1) fib(0)
fib(1) fib(0)
Es un árbol. Dice que para calcular fib (4) necesita calcular fib (3) y fib (2) y así sucesivamente.
Observe que incluso para un pequeño valor de 4, fib (2) se calcula dos veces y fib (1) se calcula tres veces. Este número de adiciones crece para números grandes.
Hay una conjetura de que el número de adiciones requeridas para calcular fib (n) es
fib(n+1) -1
Así esta duplicación es la que es la causa de la disminución del rendimiento en este algoritmo particular.
El algoritmo iterativo para la serie de Fibonacci es considerablemente más rápido ya que no implica el cálculo de las cosas redundantes.
Puede que no sea el mismo caso para todos los algoritmos.
Existen varios algoritmos iterativos para calcular la secuencia de Fibonacci y varios recursivos, con complejidad variable. –
Creo que se puede decir razonablemente que, si no tienen la misma complejidad, no son versiones iterativas y recursivas de "el mismo algoritmo". Son algoritmos diferentes y, por supuesto, diferentes algoritmos para calcular el mismo resultado no necesariamente tienen la misma complejidad. Dicho esto, es bastante común referirse a grupos de algoritmos relacionados con el mismo nombre. Por ejemplo, el quicksort se comporta de manera diferente según cómo elija el pivote y en qué orden procesa los dos lados de la partición, pero todas las posibilidades se suelen llamar "quicksort". –
... y de esto se desprende que si dos bits de código se pueden describir como "el mismo algoritmo" depende en algunos casos de si el lenguaje/compilador implementa o no la recursividad final. Si la versión recursiva crea una pila de llamadas que no necesita, entonces es un algoritmo diferente con una complejidad de espacio inferior. –