Задача 5

Условие задачи

Числа Фибоначчи $f_1, \, f_2, \, f_3, \, \ldots$ определяются условиями $f_1 = f_2 = 1$ и рекуррентным соотношением $f_n = f_{n-1} +f_{n-2}$ при $n \geqslant 3$. Докажите, что число $f_n$ при $n = 2^k$ можно вычислить за $O\left(\log_2 n\right)$ арифметических операций.

Решение задачи

Обозначим $z_n = \begin{bmatrix} f_n \\ f_{n-1} \end{bmatrix}$.

Тогда из рекуррентного соотношения $f_n = f_{n-1} + f_{n-2}$ получаем $z_n = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix} z_{n-1}$.

Обозначим $A = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}$. Тогда $z_n = A z_{n-1}$. Последовательно применяя это равенство, получаем $z_n = A^{n-2} z_2$, где $z_2 = \begin{bmatrix} f_2 \\ f_1 \end{bmatrix} = \begin{bmatrix} 1 \\ 1 \end{bmatrix}$.

Следовательно, для вычисления $f_n$ достаточно вычислить матрицу $A^{n-2}$ и умножить её на вектор $z_2$.

Так как $n = 2^k$, $n - 2 = 2^k - 2 = 2 + 2^2 + \ldots + 2^{k-1}$.

Сначала последовательным возведением в квадрат вычислим матрицы $A^2, \, A^4, \, A^8, \, \ldots, \, A^{2^{k-1}}$. Для этого требуется $k - 1$ умножений матриц.

После этого получаем $A^{n-2} = A^{2 + 2^2 + \ldots + 2^{k-1}} = A^2 A^{2^2} \ldots A^{2^{k-1}}$. Чтобы перемножить эти матрицы, требуется ровно $k - 2$ умножений.

На каждом шаге выполняется умножение двух матриц размера $2 \times 2$, т.е. фиксированное число арифметических операций.

Таким образом, общее число арифметических операций имеет порядок $O\left(k\right)$. Так как $k = \log_2 n$, получаем оценку $O\left(\log_2 n\right)$.

После вычисления матрицы $A^{n-2}$ остаётся умножить её на вектор $z_2$, что требует лишь $O\left(1\right)$ арифметических операций.

Следовательно, число Фибоначчи $f_n$ при $n = 2^k$ можно вычислить за $O\left(\log_2 n\right)$ арифметических операций. $\square$