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

Я пытаюсь найти сложность рядов Фибоначчи с использованием дерева рекурсии и заключил height of tree = O(n) худший случай, cost of each level = cn, следовательно complexity = n*n=n^2

Как получилось O(2^n)?

Ответ 1

Сложность наивного рекурсивного фибоначчи действительно равна 2ⁿ.

T(n) = T(n-1) + T(n-2) = T(n-2) + T(n-3) + T(n-3) + T(n-4) = 
= T(n-3) + T(n-4) + T(n-4) + T(n-5) + T(n-4) + T(n-5) + T(n-5) + T(n-6) = ...

На каждом шаге вы дважды вызываете T, таким образом, обеспечиваете конечный асимптотический барьер: T(n) = 2⋅2⋅...⋅2 = 2ⁿ

bonus. Лучшая теоретическая реализация фибоначчи на самом деле является close formula, используя золотое соотношение:

Fib(n) = (φⁿ – (–φ)⁻ⁿ)/sqrt(5) [where φ is the golden ratio]

(Тем не менее, он страдает от ошибок точности в реальной жизни из-за арифметики с плавающей запятой, которые не являются точными)

Ответ 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

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

Ответ 3

Посмотрите на это так. Предположим, что сложность вычисления F(k), числа kth Фибоначчи, рекурсией не более 2^k для k <= n. Это наша гипотеза индукции. Тогда сложность вычисления F(n + 1) путем рекурсии равна

F(n + 1) = F(n) + F(n - 1)

который имеет сложность 2^n + 2^(n - 1). Обратите внимание, что

2^n + 2^(n - 1) = 2 * 2^n / 2 + 2^n / 2 = 3 * 2^n / 2 <= 2 * 2^n = 2^(n + 1).

Мы показали индукцией, что утверждение, что вычисление F(k) рекурсией не более чем 2^k, является правильным.

Ответ 4

Вы правы, что глубина дерева равна O (n), но вы не выполняете O (n) работу на каждом уровне. На каждом уровне вы выполняете O (1) работу за рекурсивный вызов, но каждый рекурсивный вызов затем вносит два новых рекурсивных вызова: один на уровне ниже него и один на уровне ниже под ним. Это означает, что по мере того как вы все дальше и дальше опускаетесь по дереву рекурсии, количество вызовов на уровень растет экспоненциально.

Интересно, что вы действительно можете установить точное количество вызовов, необходимых для вычисления F (n) как 2F (n + 1) - 1, где F (n) - n-е число Фибоначчи. Мы можем доказать это индуктивно. В качестве базового случая для вычисления F (0) или F (1) нам нужно сделать ровно один вызов функции, который завершается без каких-либо новых вызовов. Скажем, что L (n) - количество вызовов, необходимых для вычисления F (n). Тогда мы имеем, что

L (0) = 1 = 2 * 1 - 1 = 2F (1) - 1 = 2F (0 + 1) - 1

L (1) = 1 = 2 * 1 - 1 = 2F (2) - 1 = 2F (1 + 1) - 1

Теперь, для индуктивного шага, предположим, что для всех n ' n, с n & ge; 2, что L (n ') = 2F (n + 1) - 1. Затем, чтобы вычислить F (n), нам нужно сделать 1 вызов исходной функции, которая вычисляет F (n), которая, в свою очередь, F (n-2) и F (n-1). По индуктивному предположению мы знаем, что F (n-1) и F (n-2) можно вычислить в L (n-1) и L (n-2) вызовах. Таким образом, общая продолжительность выполнения

1 + L (n - 1) + L (n - 2)

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

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

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

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

= 2F (n + 1) - 1

Что завершает индукцию.

В этот момент вы можете использовать формулу Binet, чтобы показать, что

L (n) = 2 (1/& radic; 5) (((1 + & radic; 5)/2) ⁿ - ((1 - & radic; 5)/2) ⁿ) - 1

И, таким образом, L (n) = O (((1 + & radic; 5)/2) ⁿ). Если мы используем соглашение, которое

& Phi; = (1 + & radic; 5)/2 & approx; 1.6

Мы имеем, что

L (n) = & Theta; (& phis; ⁿ)

И так как & phi; < 2, это o (2 ⁿ) (с использованием малой нотации).

Интересно, что я выбрал имя L (n) для этой серии, потому что этот ряд называется номерами Leonardo. В дополнение к его использованию здесь он возникает при анализе алгоритма smoothsort.

Надеюсь, это поможет!

Ответ 5

т (п) = Т (п-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 ^ п
он составит общую временную сложность = > 2 + 4 + 8 +..... 2 ^ n после решения приведенного выше gp мы получим временную сложность как O (2 ^ n)

Ответ 6

Сложность рядов Фибоначчи равна 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)).

Ответ 7

Сложность вычисления числа Фибоначчи 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;
}

Ответ 8

Сложность рекурсивного ряда Фибоначчи 2 ^ n:
Это будут рекуррентные соотношения для рекурсивного Фибоначчи

 T(n)=T(n-1)+T(n-2)                  No  of elements  2

Теперь о решении этого отношения с использованием метода подстановки (подставляя значение T (n-1) и T (n-2))

T(n)=T(n-2)+2*T(n-3)+T(n-4)          No  of elements  4=2^2

Снова подставляя значения вышеприведенного выражения, получим

T(n)=T(n-3)+3*T(n-4)+3*T(n-5)+T(n-6)  No  of elements  8=2^3

После полного его решения получаем

T(n)={T(n-k)+---------+---------}----------------------------->2^k  eq(3)

Это означает, что максимум no рекурсивных вызовов на любом уровне будет не более 2 ^ n.
И для всех рекурсивных вызовов в уравнении 3 есть Θ (1), поэтому временная сложность будет 2^n* ϴ(1)=2^n

Ответ 9

Я не могу удержаться от соблазна подключения линейного итеративного алгоритма времени для Fib к экспоненциальному рекурсивному времени: если прочитать замечательную маленькую книгу Джона Бентли "Написание эффективных алгоритмов", я считаю, что это простой случай "кэширования": всякий раз, когда вычисляется Fib (k), храните его в массиве FibCached [k]. Всякий раз, когда вызывается Fib (j), сначала проверьте, кэшируется ли она в FibCached [j]; если да, верните значение; если не использовать рекурсию. (Посмотрите на дерево вызовов сейчас...)