Complejidad computacional de la secuencia de Fibonacci

Question

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

Answer 1

modelar la función de tiempo para calcular Fib(n) como 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 es suponiendo que las evaluaciones repetidas de la misma T(n<=1) = O(1) tomar al mismo tiempo -. Es decir, no memoization es el uso

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

n

A resolver esta relación de recurrencia (mediante la generación de funciones, por ejemplo) y que va a terminar con la respuesta.

Como alternativa, se puede dibujar el árbol de la recursividad, que tendrá la profundidad O(2 e intuitiva darse cuenta de que esta función es asintóticamente ) n = 1 T(n-1) = O(2. A continuación, puede probar su conjetura por inducción.

Base: n-1 es obvio

Supongamos T(n) = O(2 ) + O(2 n-2, lo tanto

) + O(1) = O(2 que es igual a

f(n) = f(n-1) + f(n-2) T(n) Fib(n) x O(1) θ(1.6 <=> ^<=> <=>

Sin embargo, como se señala en un comentario, éste no es el apretado atado. Un hecho interesante acerca de esta función es que el T (n) es asintóticamente mismo como el valor de <=> ya que ambos se definen como

<=>.

Las hojas del árbol de la recursividad siempre devolverá 1. El valor de <=> es la suma de todos los valores devueltos por las hojas en el árbol de la recursividad, que es igual al recuento de las hojas. Puesto que cada hoja se llevará a O (1) para calcular, <=> es igual a <=>. En consecuencia, el apretado obligado para esta función es la secuencia de Fibonacci en sí (~ <=> ^<=> <=>). Puede encontrar esta apretada con destino mediante el uso de funciones generadoras como lo había mencionado anteriormente.

Answer 2

Pregúntese cuántas declaraciones deben ejecutarse 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 un^norte (a > 1):

a^norte == un^(n-1) + un^(n-2)

Dividir por un^(n-2):

a² == un + 1

Resolver a y obtienes (1+sqrt(5))/2 = 1.6180339887, también conocido como el proporción áurea.

Entonces se necesita un tiempo exponencial.

Answer 3

Hay una muy buena discusión de este problema específico más en el MIT . En la página 5, hacen que el punto de que, si se asume que una adición lleva una unidad de cálculo, el tiempo requerido para calcular Fib (N) está muy estrechamente relacionado con el resultado de Fib (N).

Como resultado, se puede saltar directamente a la muy estrecha aproximación de la serie de Fibonacci:

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

y decir, por tanto, que el peor rendimiento caso del algoritmo ingenuo es

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

PS: Hay una discusión de la cerrada Forma de expresión del número de Fibonacci enésima encima en Wikipedia si desea más información.

Answer 4

I de acuerdo con pgaur y rickerbh, la complejidad de recursivo de Fibonacci es O (2 ^ n).

llegué a la misma conclusión por un bien simplista, pero creo que el razonamiento sigue siendo válido.

En primer lugar, se trata de averiguar cuántas veces la función recursiva de Fibonacci (F () a partir de ahora) se llama a la hora de calcular el número de Fibonacci enésimo. Si se llama a una vez por número en la secuencia de 0 an, entonces tenemos O (n), si se llama a n veces para cada número, entonces tenemos O (n * n), o O (n ^ 2), y así sucesivamente.

Así que, cuando F () se llama para un número n, el número de veces F () se llama para un número dado entre 0 y n-1 aumenta a medida que nos acercamos a 0.

Como primera impresión, me parece que si lo ponemos en una forma visual, dibujo una unidad por tiempo F () es llamado para un número dado, húmeda obtener una especie de forma de pirámide (es decir, si centrar unidades horizontalmente). Algo como esto:

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

Ahora, la pregunta es, qué tan rápido es la base de esta pirámide agrandando a medida que n crece?

Vamos a dar 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 a 32 veces, que es 2 ^ 5, que para este caso de la muestra es 2 ^ (n-1).

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

Si mentalmente mover todos los * 's de F (6) a F (2) líneas en F (1) de la línea, vemos que F (1) y F (0) líneas ahora son iguales en longitud. Lo que significa, tiempos totales 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)

Answer 5

Puede ampliarlo y tener una visualizació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)

Answer 6

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 la propia 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 se puede reducir aún más utilizando su forma cerrada Si te gusta.

Answer 7

Las respuestas a prueba son buenos, pero siempre tengo que hacer un par de iteraciones a mano para convencer realmente a mí mismo. Así que sacó un pequeño árbol llamado en mi pizarra, y empecé a contar los nodos. Me dividir mis conteos a cabo en nodos totales, los nodos hoja, y los nodos interiores. Aquí 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 inmediatamente salta a es que el número de nodos de la hoja es fib(n). Lo que tomó un poco más de iteraciones a 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.

Desde el cansancio los coeficientes de la hora de clasificar la complejidad computacional, la respuesta final es θ(fib(n)).

Answer 8

complejidad de tiempo del algoritmo recursivo puede ser mejor estimada por dibujo árbol recursión, en este caso la relación de recurrencia para la elaboración de árbol recursión sería T (n) = T (n-1) + T (n-2) + O (1 ) en cuenta que cada paso toma O (1), que significa constante de tiempo, ya que hace sólo una comparación para comprobar el valor de n en si árbol block.Recursion se vería

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

A continuación, 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 a un valor particular de i, los extremos de los árboles, que caso sería cuando n-i = 1, por lo tanto, i = n-1, lo que significa que la altura del árbol es n-1. Ahora vamos a ver la cantidad de trabajo que se hace para cada uno de n capas en tree.Note que cada paso toma O (1) tiempo como se indica en 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

desde i = n-1 es la altura de la obra árbol hecho en cada nivel será

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

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

Answer 9

Bueno, en mi opinión a que se O(2^n) como en esta función sólo recursividad está tomando el tiempo considerable (divide y vencerás). Vemos que, la función anterior continuará en un árbol hasta que las hojas son aproximaciones al llegar al nivel F(n-(n-1)) decir F(1). Por lo tanto, aquí cuando anote la complejidad del tiempo encontrado en cada profundidad del árbol, la serie es la suma:

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

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

Answer 10

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

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

Answer 11

La versión ingenua de la recursividad de Fibonacci es exponencial por diseño debido a la repetición en el cálculo:

En la raíz que está calculando:

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)

A continuación, va a ser sometido 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 constante C

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 sólo un límite inferior que para el propósito de su análisis debe ser suficiente, pero la función de tiempo real es un factor de una constante por la misma fórmula de Fibonacci y la cerrado formulario es conocido por ser exponencial de la proporción áurea.

Además, se pueden encontrar versiones de Fibonacci utilizando programación dinámica como esta optimizada:

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 se ha optimizado y hacer solamente n pasos, pero también es exponencial.

Las funciones de coste se definen a partir del tamaño de entrada para el número de pasos para resolver el problema. Cuando vea la versión dinámica de Fibonacci ( n los pasos para calcular la tabla) o el algoritmo más fácil saber si un número es primo ( sqrt (n) para analizar la validez divisores del número). usted puede pensar que estos algoritmos son O (n) o O (sqrt (n)) , pero esto simplemente no es verdad por la siguiente razón: La entrada a su algoritmo es un número: n , utilizando la notación binaria el tamaño de entrada para un número entero n es log2 (n) a continuación, haciendo un cambio en la variable de

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

dejar que 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 como una función del tamaño de entrada es:

T(m) = n steps = 2^m steps

y por eso el costo es una exponencial.