Complejidad computacional de la secuencia de Fibonacci

Entiendo la notación Big-O, pero no sé cómo calcularla para muchas funciones. En particular, he estado tratando de descubrir 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?

Puede modelar la función de tiempo para calcularla 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)). Esto supone que las evaluaciones repetidas de la misma Fib(n)toman el mismo tiempo, es decir, no se utiliza ninguna memorización.

T(n<=1) = O(1)

T(n) = T(n-1) + T(n-2) + O(1)

Resuelve esta relación de recurrencia (usando funciones generadoras, por ejemplo) y terminará con la respuesta.

Alternativamente, puede dibujar el árbol de recursión, que tendrá profundidad ne intuitivamente descubrirá que esta función es asintótica . Luego puede probar su conjetura por inducción.O(2n)

Base: n = 1es obvio

Supongamos , por lo tantoT(n-1) = O(2n-1)

T(n) = T(n-1) + T(n-2) + O(1) que es igual a

T(n) = O(2n-1) + O(2n-2) + O(1) = O(2n)

Sin embargo, como se señaló en un comentario, este no es el límite. Un hecho interesante sobre esta función es que T (n) es asintóticamente igual al valor de Fib(n)ya que ambos 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 recuento 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 secuencia de Fibonacci en sí (~ ). Puede descubrir este límite apretado mediante el uso de funciones generadoras como he mencionado anteriormente.θ(1.6n)

Simplemente pregúntese cuántas declaraciones necesita ejecutar para F(n)completar.

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 con ⁿ (a> 1):

a ⁿ == a ^(n-1) + a ^(n-2)

Dividir a través de a ^(n-2) :

a ² == a + 1

Resuelve ay obtienes (1+sqrt(5))/2 = 1.6180339887, también conocido como la proporción áurea .

Entonces lleva tiempo exponencial.

Estoy de acuerdo con pgaur y rickerbh, la complejidad recursiva de fibonacci es O (2 ^ n).

Llegué a la misma conclusión con un razonamiento bastante simplista, pero creo que sigue siendo válido.

Primero, se trata de averiguar cuántas veces se llama la función recursiva de Fibonacci (F () de ahora en adelante) al calcular el enésimo número de Fibonacci. Si se llama una vez por número en la secuencia de 0 a n, entonces tenemos O (n), si se llama n veces por cada número, entonces obtenemos O (n * n) u O (n ^ 2), y así.

Entonces, cuando se llama a F () para un número n, el número de veces que se llama a 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, dibujando una unidad por cada vez que se llama F () para un número dado, obtenemos 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 aumenta 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 F (0) se llama 32 veces, que es 2 ^ 5, que para este caso de muestra es 2 ^ (n-1).

Ahora, queremos saber cuántas veces se llama a F (x), y podemos ver el número de veces que se llama a F (0) es solo una parte de eso.

Si movemos mentalmente todos los * 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 sobre este problema específico en el MIT . En la página 5, señalan que, si supone que una suma 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 Fibonacci:

Fib(N) = (1/sqrt(5)) * 1.618^(N+1) (approximately)

y decir, por lo tanto, que el peor desempeño 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 enésimo número de Fibonacci en Wikipedia si desea obtener más información.

Puedes expandirlo 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)

Está limitado en el extremo inferior por 2^(n/2)y en el extremo superior por 2 ^ n (como se señaló en otros comentarios). Y un hecho interesante de esa implementación recursiva es que tiene un estrecho límite asintótico de Fib (n) en sí. Estos hechos pueden resumirse:

T(n) = Ω(2^(n/2))  (lower bound)
T(n) = O(2^n)   (upper bound)
T(n) = Θ(Fib(n)) (tight bound)

El límite apretado se puede reducir aún más usando su forma cerrada si lo desea.

Las respuestas de prueba son buenas, pero siempre tengo que hacer algunas iteraciones a mano para convencerme realmente. Entonces dibujé un pequeño árbol de llamadas en mi pizarra y comencé a contar los nodos. Divido mis cuentas en nodos totales, nodos hoja y nodos interiores. Esto es lo que obtuve:

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 inmediatamente es que el número de nodos 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 elimina los coeficientes al clasificar la complejidad computacional, la respuesta final es θ(fib(n)).

La complejidad temporal del algoritmo recursivo se puede estimar mejor dibujando el árbol de recursión. En este caso, la relación de recurrencia para dibujar el árbol de recursión sería T (n) = T (n-1) + T (n-2) + O (1) tenga en cuenta que cada paso toma O (1), que significa tiempo constante, ya que solo hace una comparación para verificar el valor de n en el bloque if .

          n
   (n-1)      (n-2)
(n-2)(n-3) (n-3)(n-4) ...so on

Aquí digamos que cada nivel del árbol anterior se denota por i, por lo tanto,

i
0                        n
1            (n-1)                 (n-2)
2        (n-2)    (n-3)      (n-3)     (n-4)
3   (n-3)(n-4) (n-4)(n-5) (n-4)(n-5) (n-5)(n-6)

Digamos que en un valor particular de i, el árbol termina, ese caso sería cuando ni = 1, por lo tanto, i = n-1, lo que significa que la altura del árbol es n-1. Ahora veamos cuánto trabajo se realiza para cada una de las n capas en el árbol. Tenga en cuenta que cada paso lleva O (1) tiempo como se indica en la relación de recurrencia.

2^0=1                        n
2^1=2            (n-1)                 (n-2)
2^2=4        (n-2)    (n-3)      (n-3)     (n-4)
2^3=8   (n-3)(n-4) (n-4)(n-5) (n-4)(n-5) (n-5)(n-6)    ..so on
2^i for ith level

como i = n-1 es la altura del árbol, el trabajo realizado en cada nivel será

i work
1 2^1
2 2^2
3 2^3..so on

Por lo tanto, el trabajo total realizado será la suma del trabajo realizado en cada nivel, por lo tanto, será 2 ^ 0 + 2 ^ 1 + 2 ^ 2 + 2 ^ 3 ... + 2 ^ (n-1) ya que i = n-1. Por series geométricas, esta suma es 2 ^ n, por lo tanto, la complejidad del tiempo total aquí es O (2 ^ n)

Bueno, según yo, es O(2^n)como en esta función, solo la recursión está tomando un tiempo considerable (divide y vencerás). Vemos que, la función anterior continuará en un árbol hasta que las hojas se aproximen cuando alcancemos el nivel, F(n-(n-1))es decir F(1). Entonces, aquí cuando anotamos la complejidad de tiempo encontrada en cada profundidad de árbol, la serie de suma es:

1+2+4+.......(n-1)
= 1((2^n)-1)/(2-1)
=2^n -1

ese es el orden de 2^n [ O(2^n) ].

La ingenua versión 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 calculando:

F (n) depende de F (n-1) y F (n-2)

F (n-1) depende de F (n-2) nuevamente y F (n-3)

F (n-2) depende de F (n-3) nuevamente y F (n-4)

entonces está teniendo en cada nivel 2 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 constante por 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 utilizando una 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 hasta la cantidad 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 fácil 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 entero n es log2 (n) luego haciendo un cambio variable de

m = log2(n) // your real input size

descubramos 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.

Es simple de calcular mediante diagramas de llamadas a funciones. Simplemente agregue las llamadas de función para cada valor de n y observe cómo crece el número.

El Big O es O (Z ^ n) donde Z es la proporción áurea o aproximadamente 1,62.

Tanto los números de Leonardo como los de Fibonacci se acercan a esta relación a medida que aumentamos n.

A diferencia de otras preguntas Big O, no hay variabilidad en la entrada y tanto el algoritmo como la implementación del algoritmo están claramente definidos.

No hay necesidad de un montón de matemáticas complejas. Simplemente diagrama las llamadas de función a continuación y ajusta una función a los números.

O si está familiarizado con la proporción áurea, la reconocerá como tal.

Esta respuesta es más correcta que la respuesta aceptada que afirma que se acercará a f (n) = 2 ^ n. Nunca lo hará. Se acercará a f (n) = golden_ratio ^ n.

2 (2 -> 1, 0)

4 (3 -> 2, 1) (2 -> 1, 0)

8 (4 -> 3, 2) (3 -> 2, 1) (2 -> 1, 0)
            (2 -> 1, 0)


14 (5 -> 4, 3) (4 -> 3, 2) (3 -> 2, 1) (2 -> 1, 0)
            (2 -> 1, 0)

            (3 -> 2, 1) (2 -> 1, 0)

22 (6 -> 5, 4)
            (5 -> 4, 3) (4 -> 3, 2) (3 -> 2, 1) (2 -> 1, 0)
                        (2 -> 1, 0)

                        (3 -> 2, 1) (2 -> 1, 0)

            (4 -> 3, 2) (3 -> 2, 1) (2 -> 1, 0)
                        (2 -> 1, 0)

http://www.ics.uci.edu/~eppstein/161/960109.html

tiempo (n) = 3F (n) - 2