Complejidad computacional de la Secuencia de Fibonacci

Solo pregúntese cuántas instrucciones deben ejecutarse para que F(n) se 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? Prueba a ⁿ (a > 1):

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

Dividir por a ^(n-2):

A² == a + 1

Resuelve para a y obtienes (1+sqrt(5))/2 = 1.6180339887, de lo contrario conocido como el proporción áurea.

Así que toma tiempo exponencial.

Hay una muy buena discusión de este problema específico en MIT. En la página 5, hacen el punto de que, si se asume que una suma toma una unidad computacional, el tiempo requerido para calcular Fib(N) está muy estrechamente 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 decir, por lo tanto, que el peor rendimiento del caso del algoritmo ingenuo es

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

PD: Hay es una discusión de la expresión de forma cerrada del Enésimo número de Fibonacci en Wikipedia si desea más información.

Estoy de acuerdo con pgaur y rickerbh, la complejidad recursiva de fibonacci 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() a partir de ahora ) 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 para cada número, entonces obtenemos O (n*n), o O (n^2), y así sucesivamente.

Así, 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 una manera visual, dibujando una unidad por tiempo F() se llama para un número dado, wet obtener una especie de forma de pirámide (es decir, si centramos unidades horizontalmente). Algo como esto:

n              *
n-1            **
n-2           ****  
...
2           ***********
1       ******************
0    ***************************

Ahora, la pregunta es, ¿qué tan rápido se agranda la base de esta pirámide como 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 F(0) se llama 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 que el número de veces que se llama a F(0) es solo una parte de eso.

Si mentalmente movemos todas las *'s de F(6) a F(2) líneas en F(1) línea, vemos que F(1) y F(0) líneas ahora son iguales en longitud. Lo que significa, total times F () se llama 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)

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á limitada en el extremo inferior por 2^(n/2) y en el extremo superior por 2^n (como se indica en otros comentarios). Y un hecho interesante de esa implementación recursiva es que tiene un límite asintótico apretado 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. Así que dibujé un pequeño árbol de llamadas en mi pizarra y empecé a contar los nodos. Divido mis cuentas en nodos totales, nodos 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 inmediatamente 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)).

Bueno, de acuerdo a mí es O(2^n) como 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 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 del á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) ].

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

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

La versión recursiva ingenua 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) y F(n-4)

Entonces usted está teniendo en cada nivel 2 llamadas recursivas que están perdiendo una gran cantidad de 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) entonces

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 por la misma fórmula de Fibonacci y la forma cerrada se sabe que es exponencial de la razón áurea.

Además, puede encontrar versiones optimizadas de Fibonacci utilizando Dynamic programación 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];
}

Que está optimizado y hacer solo n pasos, pero también es exponencial.

Las funciones de costo se definen desde el tamaño de la entrada hasta el 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 fácil para saber si un número es primo (sqrt (n) para analizar los divisores válidos del número). usted puede pensar que estos algoritmos son O(n) o 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

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 esta es la razón por la que el costo es exponencial.

Esto funciona 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;
}