Complejidad computacional de la secuencia de Fibonacci

331

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?

Julieta
fuente
3
Vea la sección del formulario de matriz aquí: en.wikipedia.org/wiki/Fibonacci_number . Al hacer esta matriz ^ n (de una manera inteligente) puede calcular Fib (n) en O (lg n). El truco está en hacer la función de potencia. Hay una muy buena conferencia en iTunesU sobre este problema exacto y cómo resolverlo en O (lg n). El curso es una introducción a los algoritmos de la lección 3 del MIT (es totalmente gratuito, así que échale un vistazo si estás interesado)
Aly
1
Ninguno de los comentarios anteriores aborda la pregunta, que trata sobre la complejidad computacional de la versión ingenua (en el código publicado), no sobre versiones más inteligentes como la forma de matriz o el cálculo no recursivo.
Josh Milthorpe
Un video muy agradable aquí que habla sobre la complejidad del límite inferior (2 ^ n / 2) y la complejidad del límite superior (2 ^ n) de la implementación recursiva.
RBT
1
Una consulta al margen: ¿la implementación ingenua de la serie Fibonacci debe ser iterativa o recursiva ?
RBT

Respuestas:

375

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)

Mehrdad Afshari
fuente
29
También prueba por inducción. Agradable. +1
Andrew Rollings
Aunque el límite no es apretado.
Capitán Segfault
@ Capitán Segfault: Sí. Aclaré la respuesta. Obtendría el límite estricto utilizando el método GF como había escrito anteriormente.
Mehrdad Afshari
Itake su StackOverflowException como una broma. El tiempo exponencial es perceptible con bastante facilidad con valores bastante pequeños para n.
David Rodríguez - dribeas
1
"Alternativamente, puede dibujar el árbol de recursión, que tendrá profundidad n e intuitivamente descubrirá que esta función es asintóticamente O (2n)". - Esto es completamente falso. La complejidad del tiempo es O (golden_ratio ^ n). Nunca se acerca a O (2 ^ n). Si pudieras alcanzar el infinito, se acercaría a O (golden_ratio ^ n). Eso es lo que es una asíntota, la distancia entre las dos líneas debe acercarse a 0.
bob
133

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

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

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

a 2 == a + 1

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

Entonces lleva tiempo exponencial.

Jason Cohen
fuente
8
Prueba por inducción. Agradable. +1
Andrew Rollings
2
¿30 votos a favor por una respuesta incorrecta? :-) ¿Se deduce que 1 = F (1) = (1 + sqrt (5)) / 2? ¿Y qué hay de la otra solución, (1-sqrt (5)) / 2?
Carsten S
1
No, 1 no es igual a 1 + 1. La función que satisface esas reglas se menciona en la pregunta.
molbdnilo
66
La respuesta no es incorrecta. Está bien asintomáticamente. La otra solución es negativa, por lo que físicamente no tiene sentido.
Da Teng
10
¿Alguien puede explicar cómo a ^ n == a ^ (n-1) + a ^ (n-2) satisface estas reglas? ¿Cómo se satisface exactamente? Sea específico.
Frank
33

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)
JP
fuente
3
F (3) solo se llama 3 veces y no 4 veces. La segunda pirámide está mal.
Avik
2
F (3) = 3, F (2) = 5, F (1) = 8, F (0) = 5. Lo arreglaría, pero no creo que pueda salvar esta respuesta con una edición.
Bernhard Barker
31

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.

Bob Cross
fuente
Gracias por el enlace del curso. Muy buena observación también
SwimBikeRun
16

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)
Tony Tannous
fuente
1
Entiendo la primera línea. Pero, ¿por qué hay un carácter inferior <al final? ¿Cómo se consigue T(n-1) + T(n-1)?
Quazi Irfan
@QuaziIrfan: D eso es una flecha. -> [(no menos de). Perdón por la confusión con respecto a la última línea]. Para la primera línea, bueno ... T(n-1) > T(n-2)Entonces puedo cambiar T(n-2)y poner T(n-1). Yo sólo obtiene una consolidados más altos que sigue siendo válida paraT(n-1) + T(n-2)
a Tony Tanus
10

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.

Dave L.
fuente
10

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

benkc
fuente
(No, no dibujé un árbol de llamadas completo de 10 de profundidad en mi pizarra. Solo 5 de profundidad.);)
benkc
Agradable, me preguntaba cuántas adiciones adicionales hizo Fib recursiva. No es sólo la adición 1de un único acumulador Fib(n)veces, pero interesante que sigue siendo exactamente θ(Fib(n)).
Peter Cordes
Tenga en cuenta que algunas (la mayoría) implementaciones recursivas pasan tiempo agregando 0, sin embargo: los casos base de recursividad son 0y 1, porque lo hacen Fib(n-1) + Fib(n-2). Entonces, probablemente la respuesta3 * Fib(n) - 2 de este enlace solo sea ​​más precisa para el número total de nodos, no 2 * Fib(n) - 1.
Peter Cordes
No puedo obtener los mismos resultados en los nodos de hoja. A partir de 0: F (0) -> 1 hoja (sí mismo); F (1) -> 1 hoja (sí mismo); F (2) -> 2 hojas (F (1) y F (0)); F (3) -> 3 hojas; F (5) -> 8 hojas; etc.
alexlomba87
9

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)

nikhil kekan
fuente
2

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) ].

pgaur
fuente
1

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.

Miguel
fuente
1

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)
Beto
fuente
1
¿Puede proporcionar alguna fuente para esa afirmación sobre la proporción áurea?
Nico Haase