Решая повторение по Фибоначчи в логарифмическом времени

Question

Нахождение n-го члена в ряду Фибоначчи f (n) = f (n-1) + f (n-2) может быть решено за O (n) время путем запоминания.

Более эффективным способом было бы найти n-ую степень матрицы [[1,1], [1,0]] с использованием деления и завоевания для решения Фибоначчи за логарифмическое время.

Есть ли подобный подход, которому можно следовать для f (n) = f (n-1) + f (n-x) + f (n-x + 1) [x - некоторая константа].

Просто сохраните предыдущие элементы x, это можно решить за O (n) раз.

Есть ли лучший способ решить эту рекурсию.

Answer 1

Как вы уже подозреваете, это будет работать очень похоже.Используйте n-ю степень матрицы x * x

|1 0 0 0  .... 1 1|
|1 
|  1
|    1
|      1
|        1
...................
...................
|          ... 1 0|

Это легко понять, если умножить эту матрицу на вектор

f(n-1), f(n-2), ... , f(n-x+1), f(n-x)

, что приведет к

f(n), f(n-1), ... , f(n-x+1)

Матричное возведение в степень может быть выполнено за O (log (n)) время (когда x считается постоянным).

Для рекурсии Фибоначчи также есть решение с замкнутой формулой, см. Здесьhttp://en.wikipedia.org/wiki/Fibonacci_number, ищите формулу Бине или Моивра.

Answer 2

Возможно, вы захотите взглянуть на числа Трибоначи (и другие обобщения чисел Фибониачи). Они изучены достаточно широко.Смотрите, например, Обобщения чисел Фибоначчи