Почему сложность вычисления ряда Фибоначчи составляет 2 ^ n, а не n ^ 2?

Дерево рекурсии для fib (n) будет выглядеть примерно так:

                              n       
                           /     \
                          n-1    n-2      --------- maximum 2^1 additions
                         /  \    /   \
                       n-2   n-3 n-3 n-4  -------- maximum 2^2 additions
                      /   \           
                     n-3 n-4              -------- maximum 2^3 additions         
                                                ........
                                          -------- maximum 2^(n-1) additions  

1. Использование n-1 в 2 ^ (n-1), поскольку для fib (5) мы в конечном итоге перейдем вплоть до фиб (1)
2. Количество внутренних узлов = Количество листьев - 1 = 2 ^ (n-1) - 1
3. Количество сложений = Количество внутренних узлов + Количество листьев = (2 ^ 1 + 2 ^ 2 + 2 ^ 3 + ...) + 2 ^ (n-1)
4. Мы можем заменить количество внутренних узлов на 2 ^ (n-1) - 1 потому что оно всегда будет меньше, чем это значение: = 2 ^ (n-1) - 1 + 2 ^ (n-1) ~ 2 ^ n

t (n) = t (n-1) + t (n-2), которые могут быть решены с помощью древовидного метода:

                                  t(n-1)  +  t(n-2)        2^1=2
                                   |         |  
                            t(n-2)+t(n-3)  t(n-3)+t(n-4)   2^2=4  
                                .               .          2^3=8
                                .               .           .
                                .               .           .

аналогично для последнего уровня. , 2 ^ n
это сделает общую временную сложность => 2 + 4 + 8 + ..... 2 ^ n после решения вышеупомянутого gp мы получим временную сложность как O (2 ^ n)

Сложность ряда Фибоначчи составляет O (F (k)), где F (k) - это k-е число Фибоначчи. Это можно доказать по индукции. Это тривиально для обоснованного случая. И предположим, что для всех k < = n сложность вычисления F (k) равна c * F (k) + o (F (k)), тогда для k = n + 1 сложность вычисления F (n + 1). ) это c * F (n) + o (F (n)) + c * F (n-1) + o (F (n-1)) = c * (F (n) + F (n-1) ) + o (F (n)) + o (F (n-1)) = O (F (n + 1)).

Сложность O (2 ^ n) вычисления числа Фибоначчи применима только к рекурсивному подходу. С небольшим дополнительным пространством вы можете добиться гораздо лучшей производительности с помощью O (n).

public static int fibonacci(int n) throws Exception {

  if (n < 0)
    throws new Exception("Can't be a negative integer")

  if (n <= 1)
    return n;

  int s = 0, s1 = 0, s2 = 1;
  for(int i= 2; i<=n; i++) {
    s = s1 + s2;
    s1 = s2;
    s2 = s;            
  }
  return s;
}