Решение рекурсии в числах Фибоначчи

Question

Я не знаю о математике в этом алгоритме и мог бы помочь.

Алгоритм:

if n<2 then

  return n

else return fibonacci(n-1) + fibonacci(n-2)

Заявление

n <2 - O (1) <br> Время n> = 2 равно O (1)
Возвращаемое значение равно 0 (1) Время n> = 2 - Возвращаемое значение fib (n-1) + fib (n-2) равно -

и время n> = 2 равно T (n-1) + T (n-2) + O (1)

Всего: O (1) T (n-1) + T (n-2) + O (1)
T (n) = O (1), если n <2 <br> T (n) = T (n-1) + T (n-2) + O (1), если n> = 2

Answer 1

Я думаю, вы должны заметить, что отношение повторения для этой функции ужасно знакомо . Вы можете точно узнать, насколько быстро растет это очень знакомое повторение, посмотрев его по имени.

Однако, если вам не удастся сделать интуитивный скачок, вы можете попытаться ограничить время выполнения, используя упрощенную задачу. По сути, вы модифицируете алгоритм таким образом, чтобы гарантированно увеличить время выполнения, упрощая его. Затем вы выясняете время выполнения нового алгоритма, который дает вам верхнюю границу.

Например, этот алгоритм должен занимать больше времени и его проще анализировать:

F(n): if n<2 then return n else return F(n-1) + F(n-1)

Answer 2

По индукции: если вычисление fib(k) занимает меньше C*2^k для всех k < n, то для расчета fib(n) мы получаем

T(n) = T(n-1) + T(n-2) + K < C*2^(n-1) + С*2^(n-2) + K
     = 0.75*C*2^n + K < C*2^n

для достаточно большого C (для C > K/0.25, как 2^n > 1). Это доказывает, что T(n) < C*2^n, т.е. T(n) = O(2^n).

(Здесь T(n) - это время для расчета fib(n), K - это постоянное время, необходимое для расчета fib(n), когда и fib(n-1), и fib(b-1) [уже] рассчитаны.)

Answer 3

Вам необходимо решить уравнение повторения:

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