Свойства алгоритма плохого Фибоначчи

Question

Я смотрел на канонический алгоритм плохих фибоначчи на днях:

public static int fib(int n)
{
    // Base Case
    if (n < 2)
    return 1;       
    else 
    return fib(n-1) + fib(n-2);     
}

Я сделал интересное наблюдение. Когда вы вызываете fib (n), то для k от 1 до n fib (k) называется точно fib (n-k + 1) раз (или fib (n-k) в зависимости от вашего определения fib (0)). Кроме того, fib (0) называется fib (n-k-1) раз. Затем это позволяет мне обнаружить, что в fib (100) есть ровно 708449696358523830149 вызовов функции fib.

Есть ли другие интересные наблюдения по этой функции, о которых вы знаете?

Дополнительное примечание: я знаю все интересные вещи о запоминании и т. Д. Я НЕ спрашиваю, как его оптимизировать.

Answer 1

В добавление к тому, что сказал Ювал ...

Помимо запоминания, стоит упомянуть тесно связанное " динамическое программирование ". Очень тесно связаны - лично мне не очень ясно, является ли запоминание частным случаем динамического программирования или нет.В любом случае, в этом случае стандартное итеративное решение можно назвать решением динамического программирования.

В итеративном решении, когда вы пытаетесь вычислить fib(n), вы уже вычислили частичные решения fib(n-2) и fib(n-1) так что вы просто повторно используете эти предварительно рассчитанные частичные решения.То, что это делается в цикле, не важно для динамического программирования.Мемоизация может быть особым случаем (я просто не уверен, всегда ли это особый случай согласно строгим определениям).Ключевым моментом является то, что каждое частичное решение запоминается, поэтому его нужно вычислять только один раз.

Answer 2

Это прекрасный пример того, почему памятка является очень полезной оптимизацией для таких функций, как Фибоначчи.

Как видите, вы можете уменьшить количество вызовов функций с 2*fib(n)-1 до n - что на несколько порядков лучше.

Математически числа Фибоначчи обладают многими другими интересными свойствами.

Answer 3

Я просто добавлю эту более математическую заметку. Большая запись O для вашего алгоритма действительно F (n), но что, черт возьми, это значит по сравнению с O (N ^ 2) или O (NlogN), которые мы обычно думать о?

Это безумно плохо: у него есть O (e ^ N) пространственно-временная сложность. Математически вы можете показать, что lim (N-> \ inf) F (n) = ((1+ \ sqrt (5)) / 2) ^ N