time-complexity - serie - sucesion de fibonacci ejercicios
Complejidad computacional de la secuencia de Fibonacci (11)
Bueno, según yo, es O(2^n) ya que en esta función solo la recursión está tomando el tiempo considerable (divide y vencerás). Vemos que la función anterior continuará en un árbol hasta que las hojas se acerquen cuando alcancemos el nivel F(n-(n-1)) es decir, F(1) . Entonces, aquí cuando anotamos la complejidad del tiempo encontrado en cada profundidad de árbol, la serie de resumen es:
1+2+4+.......(n-1)
= 1((2^n)-1)/(2-1)
=2^n -1
es decir, orden de 2^n [ O(2^n) ] .
Entiendo la notación Big-O, pero no sé cómo calcularla para muchas funciones. En particular, he estado tratando de averiguar la complejidad computacional de la versión ingenua de la secuencia de Fibonacci:
int Fibonacci(int n)
{
if (n <= 1)
return n;
else
return Fibonacci(n - 1) + Fibonacci(n - 2);
}
¿Cuál es la complejidad computacional de la secuencia de Fibonacci y cómo se calcula?
Está limitado en el extremo inferior por 2^(n/2) y en el extremo superior por 2 ^ n (como se señala en otros comentarios). Y un hecho interesante de esa implementación recursiva es que tiene un estrecho límite asintótico de Fib (n). Estos hechos se pueden resumir:
T(n) = Ω(2^(n/2)) (lower bound)
T(n) = O(2^n) (upper bound)
T(n) = Θ(Fib(n)) (tight bound)
El límite ajustado puede reducirse aún más utilizando su forma cerrada si lo desea.
Esto se realiza mucho mejor:
unsigned int Fib(unsigned int n)
{
// first Fibonaci number is Fib(0)
// second one is Fib(1) and so on
// unsigned int m; // m + current_n = original_n
unsigned int a = 1; // Fib(m)
unsigned int b = 0; // Fib(m-1)
unsigned int c = 0; // Fib(m-2)
while (n--)
{
c = b;
b = a;
a = b+c;
}
return a;
}
Estoy de acuerdo con pgaur y rickerbh, la complejidad de la fibonacci recursiva es O (2 ^ n).
Llegué a la misma conclusión por un razonamiento bastante simplista, pero creo que sigue siendo válido.
Primero, se trata de averiguar cuántas veces se llama a la función de fibonacci recursiva (F () de ahora en adelante) cuando se calcula el número Nth de fibonacci. Si se llama una vez por número en la secuencia 0 a n, entonces tenemos O (n), si se llama n veces por cada número, obtenemos O (n * n), o O (n ^ 2), y así.
Entonces, cuando se llama F () para un número n, el número de veces que se llama F () para un número dado entre 0 y n-1 crece a medida que nos acercamos a 0.
Como primera impresión, me parece que si lo ponemos de manera visual, al dibujar una unidad por tiempo se llama F () para un número dado, obtener una especie de forma piramidal (es decir, si centramos las unidades horizontalmente ). Algo como esto:
n *
n-1 **
n-2 ****
...
2 ***********
1 ******************
0 ***************************
Ahora, la pregunta es, ¿qué tan rápido se está agrandando la base de esta pirámide a medida que n crece?
Tomemos un caso real, por ejemplo F (6)
F(6) * <-- only once
F(5) * <-- only once too
F(4) **
F(3) ****
F(2) ********
F(1) **************** <-- 16
F(0) ******************************** <-- 32
Vemos que se llama a F (0) 32 veces, que es 2 ^ 5, que para este caso de ejemplo es 2 ^ (n-1).
Ahora, queremos saber cuántas veces se llama a F (x) y podemos ver la cantidad de veces que se llama a F (0) es solo una parte de eso.
Si movemos mentalmente todos los * ''s de las líneas F (6) a F (2) a la línea F (1), vemos que las líneas F (1) y F (0) ahora tienen la misma longitud. Lo que significa que se llama a F () cuando n = 6 es 2x32 = 64 = 2 ^ 6.
Ahora, en términos de complejidad:
O( F(6) ) = O(2^6)
O( F(n) ) = O(2^n)
Hay una muy buena discusión de este problema específico en MIT . En la página 5, señalan que, si asume que una adición requiere una unidad computacional, el tiempo requerido para calcular Fib (N) está muy relacionado con el resultado de Fib (N).
Como resultado, puede saltar directamente a la aproximación muy cercana de la serie de Fibonacci:
Fib(N) = (1/sqrt(5)) * 1.618^(N+1) (approximately)
y digamos, por lo tanto, que el peor desempeño del caso del algoritmo ingenuo es
O((1/sqrt(5)) * 1.618^(N+1)) = O(1.618^(N+1))
PD: hay una discusión sobre la expresión de forma cerrada del número Nth Fibonacci en Wikipedia si desea obtener más información.
La versión ingenua de recursión de Fibonacci es exponencial por diseño debido a la repetición en el cálculo:
En la raíz estás computando:
F (n) depende de F (n-1) y F (n-2)
F (n-1) depende de F (n-2) de nuevo y F (n-3)
F (n-2) depende de F (n-3) de nuevo y F (n-4)
entonces, en cada nivel 2, hay llamadas recursivas que están desperdiciando muchos datos en el cálculo, la función de tiempo se verá así:
T (n) = T (n-1) + T (n-2) + C, con C constante
T (n-1) = T (n-2) + T (n-3)> T (n-2) luego
T (n)> 2 * T (n-2)
...
T (n)> 2 ^ (n / 2) * T (1) = O (2 ^ (n / 2))
Esto es solo un límite inferior que para el propósito de su análisis debería ser suficiente, pero la función en tiempo real es un factor de una constante de la misma fórmula de Fibonacci y se sabe que la forma cerrada es exponencial de la proporción áurea.
Además, puede encontrar versiones optimizadas de Fibonacci usando programación dinámica como esta:
static int fib(int n)
{
/* memory */
int f[] = new int[n+1];
int i;
/* Init */
f[0] = 0;
f[1] = 1;
/* Fill */
for (i = 2; i <= n; i++)
{
f[i] = f[i-1] + f[i-2];
}
return f[n];
}
Eso está optimizado y solo hace n pasos pero también es exponencial.
Las funciones de costo se definen desde el tamaño de entrada al número de pasos para resolver el problema. Cuando vea la versión dinámica de Fibonacci ( n pasos para calcular la tabla) o el algoritmo más sencillo para saber si un número es primo ( sqrt (n) para analizar los divisores válidos del número). puede pensar que estos algoritmos son O (n) u O (sqrt (n)) pero esto simplemente no es cierto por la siguiente razón: la entrada a su algoritmo es un número: n , usando la notación binaria el tamaño de entrada para un el entero n es log2 (n) y luego hace un cambio de variable de
m = log2(n) // your real input size
Vamos a averiguar el número de pasos en función del tamaño de entrada
m = log2(n)
2^m = 2^log2(n) = n
entonces el costo de su algoritmo en función del tamaño de entrada es:
T(m) = n steps = 2^m steps
Y es por eso que el costo es exponencial.
Las respuestas de la prueba son buenas, pero siempre tengo que hacer algunas iteraciones a mano para realmente convencerme. Así que dibujé un pequeño árbol de llamadas en mi pizarra y comencé a contar los nodos. Divido mis cuentas en nodos totales, nodos de hoja y nodos interiores. Esto es lo que tengo:
IN | OUT | TOT | LEAF | INT
1 | 1 | 1 | 1 | 0
2 | 1 | 1 | 1 | 0
3 | 2 | 3 | 2 | 1
4 | 3 | 5 | 3 | 2
5 | 5 | 9 | 5 | 4
6 | 8 | 15 | 8 | 7
7 | 13 | 25 | 13 | 12
8 | 21 | 41 | 21 | 20
9 | 34 | 67 | 34 | 33
10 | 55 | 109 | 55 | 54
Lo que salta de inmediato es que el número de nodos de la hoja es fib(n) . Lo que tomó algunas iteraciones más para notar es que el número de nodos interiores es fib(n) - 1 . Por lo tanto, el número total de nodos es 2 * fib(n) - 1 .
Dado que se eliminan los coeficientes al clasificar la complejidad computacional, la respuesta final es θ(fib(n)) .
Modela la función de tiempo para calcular Fib(n) como la suma de tiempo para calcular Fib(n-1) más el tiempo para calcular Fib(n-2) más el tiempo para sumarlos ( O(1) ).
T(n<=1) = O(1)
T(n) = T(n-1) + T(n-2) + O(1)
Resuelve esta relación de recurrencia (utilizando funciones de generación, por ejemplo) y terminará con la respuesta.
Alternativamente, puede dibujar el árbol de recursión, que tendrá profundidad n y entenderá de manera intuitiva que esta función es asintóticamente O(2 n ) . A continuación, puede probar su conjetura por inducción.
Base: n = 1 es obvio
Supongamos T(n-1) = O(2 n-1 ) , por lo tanto
T(n) = T(n-1) + T(n-2) + O(1) que es igual a
T(n) = O(2 n-1 ) + O(2 n-2 ) + O(1) = O(2 n )
Sin embargo, como se señaló en un comentario, este no es el límite estrecho. Un hecho interesante acerca de esta función es que la T (n) es asintóticamente igual al valor de Fib(n) ya que ambas se definen como
f(n) = f(n-1) + f(n-2) .
Las hojas del árbol de recursión siempre devolverán 1. El valor de Fib(n) es la suma de todos los valores devueltos por las hojas en el árbol de recursión que es igual al conteo de hojas. Como cada hoja tomará O (1) para calcular, T(n) es igual a Fib(n) x O(1) . En consecuencia, el límite estricto para esta función es la propia secuencia de Fibonacci (~ θ(1.6 n ) ). Puede descubrir este límite estrecho mediante el uso de funciones de generación como lo mencioné anteriormente.
Puedes ampliarlo y tener una visulización.
T(n) = T(n-1) + T(n-2) <
T(n-1) + T(n-1)
= 2*T(n-1)
= 2*2*T(n-2)
= 2*2*2*T(n-3)
....
= 2^i*T(n-i)
...
==> O(2^n)
Solo pregúntese cuántas sentencias deben ejecutarse para que F(n) complete.
Para F(1) , la respuesta es 1 (la primera parte del condicional).
Para F(n) , la respuesta es F(n-1) + F(n-2) .
Entonces, ¿qué función satisface estas reglas? Pruebe una n (a> 1):
a n == a (n-1) + a (n-2)
Divide a través de un (n-2) :
a 2 == a + 1
Resuelve para a y obtienes (1+sqrt(5))/2 = 1.6180339887 , también conocido como la proporción de oro .
Así que lleva tiempo exponencial.
http://www.ics.uci.edu/~eppstein/161/960109.html
tiempo (n) = 3F (n) - 2