Почему время Фибоначчи θ (1,6 ^ N)?

Question

Почему время выполнения ближе к O (1,6 ^ N), а не к O (2 ^ N)?Я думаю, что это как-то связано со стеком вызовов, но мне все еще немного непонятно.

int Fibonacci(int n)
{
    if (n <= 1)
        return n;
    else
        return Fibonacci(n - 1) + Fibonacci(n - 2);
}

Answer 1

Для начала помните, что нотация big-O всегда обеспечивает верхнюю границу.То есть, если функция является O (n), это также O (n ² ), O (n ³ ), O (2 ⁿ ),и т.д. Таким образом, в этом смысле вы не ошибаетесь, если говорите, что время выполнения равно O (2 ⁿ ).У вас просто нет жесткой границы.

Чтобы увидеть, откуда исходит жесткая граница Θ (φ ⁿ ), это может помочь выяснить, сколько рекурсивных вызовов в конечном итоге получаютсделано при оценке Fibonacci(n).Обратите внимание, что для

• Fibonacci(0) требуется один вызов, для вызова Fibonacci(0).
• Fibonacci(1) требуется один вызов, для вызова Fibonacci(1).
• Fibonacci(3) требует пять вызовов: один на Fibonacci(3), затем три сгенерированных вызовапутем вызова Fibonacci(2) и одного вызова, генерируемого путем вызова Fibonacci(1).
• Fibonacci(4), требуется девять вызовов: один на Fibonacci(4), затем пять от вызова на Fibonacci(3) и три от вызова наFibonacci(2).

В более общем случае картина выглядит так: если вы звоните Fibonacci(n) для некоторого n ≥ 2, то количество сделанных вызовов равно одному (для самого вызова)плюс количество звонков, необходимое для оценки Fibonacci(n-1) и Fibonacci(n-2).Если мы допустим, что L _n обозначает количество совершенных вызовов, это означает, что у нас есть

• L ₀ = L ₁ = 1
• L _{n + 2} = 1 + L _n + L _{n + 1} .

Итак, теперь вопрос в том, насколько быстро эта последовательность растет.Оценка первых нескольких терминов дает нам

1, 1, 3, 5, 9, 15, 25, 41, ...

, который определенно становится все больше и больше, но не ясно, насколько оно больше.

Здесь вы можете заметить, что L _n своего рода сортировка выглядит как числа Фибоначчи.То есть он определен в терминах суммы двух предыдущих терминов, но у него есть дополнительный член +1.Поэтому, возможно, нам стоит взглянуть на разницу между L _n и F _n , поскольку это может показать нам, насколько «быстрее» растет серия L.Вы можете заметить, что первые два значения ряда L равны 1, 1, а первые два значения ряда Фибоначчи равны 0, 1, поэтому мы будем сдвигать все на один член, чтобы все выстроилось в ряд:

L(n)     1   1   3   5   9  15  25  41
F(n+1)   1   1   2   3   5   8  13  21
Diff:    0   0   1   2   4   7  12  20

И подождите, подождите секунду.Что произойдет, если мы добавим один к каждому члену разницы?Это дает нам

L(n)     1   1   3   5   9  15  25  41
F(n+1)   1   1   2   3   5   8  13  21
Diff+1   1   1   2   3   5   8  13  21

Вау!Выглядит как L _n - F _{n + 1} + 1 = F _{n + 1} .Переставляя, мы видим, что

L _n = 2F _{n + 1} - 1.

Ух ты!Таким образом, фактическое количество вызовов, сделанных рекурсивной функцией Фибоначчи, очень тесно связано с возвращаемым фактическим значением.Таким образом, мы могли бы сказать, что время выполнения функции Фибоначчи Θ (F _{n + 1} ), и мы были бы правы.

Но теперь вопрос в том, откуда приходит φ.Прекрасный математический результат называется Формула Бине , который говорит, что F _n = Θ (φ ⁿ ).Есть много способов доказать это, но все они по сути сводятся к наблюдению, что

1. числа Фибоначчи, кажется, растут экспоненциально быстро;
2. , если они растут экспоненциально с базойx, тогда F _{n + 2} = F _n + F _{n + 1} можно переписать как x ² = x + 1;и
3. φ является решением x ² = x + 1.

Из этого мы можем видеть, что поскольку время выполнения Фибоначчи равно Θ (F _{n + 1} ), тогда время выполнения также равно Θ (φ ^{n + 1} ) = Θ (φ ⁿ ).

Answer 2

Число ϕ = (1+sqrt(5))/2 характеризуется двумя следующими свойствами:

1. ϕ >= 1
2. ϕ^2 = ϕ + 1.

Умножив второе уравнение на ϕ^{n-1}, мы получим

3. ϕ^{n+1} = ϕ^n + ϕ^{n-1}

Начиная с f(0) = 0, f(1) = 1 и f(n+1) = f(n) + f(n-1), используя 1 и 3 , легко узнать по индукции в n, что

f(n) <= ϕ^n

Таким образом f(n) есть O(ϕ^n).

Аналогичный индуктивный аргумент показывает, что

f(n) >= ϕ^{n-3} = ϕ^{-3}ϕ^n      (n >= 1)

таким образом f(n) = θ(ϕ^n).