Обобщенный Фибоначчи

Question

Как найти n-й член повторения в log(n) времени.

F[n]=F[n-1]+F[n-3]
F[2]=1;
F[3]=2;
F[4]=3;
F[5]=4;

Я не мог создать необходимую матрицу для возведения в степень. Извините, если это кажется не по теме.

Спасибо, но я нашел ответ. https://math.stackexchange.com/questions/891964/generalised-fibonacci/891979

Answer 1

N-е число Фибноначи определяется как:

f(n) = Floor(phi^n / sqrt(5) + 1/2)

где

phi = (1 + sqrt(5)) / 2

Предполагая, что примитивные математические операции (+, -, * и /) равны O(1), вы можете использовать этот результат для вычисления n-го числа Фибоначчи за O(log n) времени (O(log n) из-за возведения в степень в формула).

Применительно к: n-му числу Фибоначчи в сублинейном времени