Как я могу вычислить эффективность этого алгоритма Фибоначчи?

Question

Я использую ракетка (и производной схемы/Lisp), и я написал этот алгоритм Фибоначчи, который использует Гидроаккумуляторы:

(define (fibonacci* n) 
    (local (; NaturalNumber NaturalNumber NaturalNumber -> NaturalNumber 
      ; Add accumulators for current and previous fibonacci numbers 
      (define (fibonacci-acc x current previous) 
      (if (= x n) current 
       (fibonacci-acc (add1 x) (+ current previous) current)))) 
    (fibonacci-acc 0 0 1))) 

Это большой шаг вперед по сравнению с функцией, которая не использует аккумуляторы, как следующее :

(define (fibonacci n) 
    (if (<= n 1) n 
     (+ (fibonacci (- n 1)) 
     (fibonacci (- n 2))))) 

Но как я могу установить рекуррентные уравнения для расчета как много более эффективным это?

Answer 1

Пусть Т (п) время, чтобы вычислить (fib n) где fib является:

(define (fib n) 
    (if (<= n 1) 
     n 
     (+ (fib (- n 1)) 
     (fib (- n 2))))) 

Поскольку тело fib имеет условный (if (<= n 1) ...) нам нужно рассмотреть два случая.

Если n < = 1, то оценивается выражение n. Это переменная ссылка, и она занимает постоянное время. Установите время в 1 (единица времени).

Короче говоря, мы имеем:

T(0) = 1 
T(1) = 1 

Для п больше, чем 1, то выражение (+ (fib (- n 1)) (fib (- n 2))))) оценивается. Время, необходимое для оценки (fib (- n 1)), по определению T точно T (n-1). Аналогично, для вычисления (fib (- n 2)))) требуется время T (n-2).Затем добавляются результаты двух подвыражений (+ ...). Время, затрачиваемое на добавление двух исправлений (63-битных чисел), более или менее совпадает с временем ссылки на переменные. Таким образом, мы устанавливаем время, чтобы сделать добавление к 1. Вместе мы получаем, что:

T(n) = 1 + T(n-1) + T(n-2) for n>1 

Три рекуррентные уравнения таковы:

T(0) = 1 
T(1) = 1 
T(n) = 1 + T(n-1) + T(n-2) for n>1 

См стр.8 следующего документа для анализа Т :

http://users.cecs.anu.edu.au/~peter/seminars/RunningTimeInduction.

По индукции доказано, что T(n)<=2^n.

Answer 2

Ну, это легко, если вы вычислите новый номер, вы просто возьмете два меньших числа, которые вы уже знаете.

Каждое новое число вычисляется в постоянное время.

Следовательно, сложность для n-го числа фионначчи является O (n) - линейной.

Answer 3

Вторая функция вычисляет одну и ту же вещь несколько раз, поэтому ее сложность экспоненциальна (O(2^n), вы можете получить лучшую оценку, но она находится в этом шале).

  f(5) 
    / \ 
    f(3) f(4) 
/| / \ 
f(1) f(2) f(2) f(3) 
     / \ | \ 
     f(0) f(1) f(1) f(2) 
         / \ 
         f(0) f(1) 

Как вы можете видеть рисунок дерева рекурсии, даже при малых значениях несколько значений пересчитываются очень часто.

Чтобы увидеть, что это действительно экспоненциальный, представьте дерево для f(6): он будет содержать это дерево, так как оно вызывает f(5) и дерево для f(4), так что это будет дерево почти в два раза размер.

Решение, использующее аккумуляторы, позволяет избежать этого, найдя нужный номер фибоначчи снизу вверх, таким образом, только вычисляя то, что абсолютно необходимо. Это делает его O(n), чтобы получить n -й номер фибоначчи.

Чтобы получить представление о том, насколько более эффективным первый алгоритм, рассмотрим, как линейная функция растет по сравнению с экспоненциальной:

n | 2^n 
=========== 
1 | 2 
2 | 4 
3 | 8 
4 | 16 
5 | 32 
6 | 64 

Так в основном, линейный намного быстрее, в самом деле, как вы Экспериментально установлено.