Задача 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(\log_2 n)$ арифметических операций.

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

Доопределим $f_0 := 0$. Тогда соотношение $f_n = f_{n-1} + f_{n-2}$ становится верным и при $n = 2$ ($f_2 = f_1 + f_0 = 1 + 0 = 1$), а не только при $n \geqslant 3$.

Соберём два соседних числа Фибоначчи в столбец $z_n = \begin{bmatrix} f_{n+1} \\ f_{n} \end{bmatrix}$ (в частности, $z_0 = \begin{bmatrix} 1 \\ 0 \end{bmatrix}$) и введём матрицу $A = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}$.

Получим $Az_n = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix} \begin{bmatrix} f_{n+1} \\ f_n \end{bmatrix} = \begin{bmatrix} f_{n+1} + f_n \\ f_{n+1} \end{bmatrix}$.

По рекуррентному соотношению $f_{n+1} + f_n = f_{n+2}$ (оно верно при $n + 2 \geqslant 2$, то есть при всех $n \geqslant 0$) $Az_n = \begin{bmatrix} f_{n+2} \\ f_{n + 1} \end{bmatrix} = z_{n+1}$.

Применим индукцию и покажем, что $z_n = A^n z_0$: база – $z_0 = A^0 z_0$ тождественна, шаг – $z_{n+1} = A z_n = A \left(A^n z_0\right) = A^{n+1} z_0$. Итак, $z_n = A^n z_0 = A^n \begin{bmatrix} 1 \\ 0 \end{bmatrix}$.

Умножение $A^n$ на $\begin{bmatrix} 1 \\ 0 \end{bmatrix}$ просто «вырезает» первый столбец матрицы $A^n$. Значит, $z_n$ – первый столбец $A^n$, а искомое $f_n = \left(z_n\right)_2 = \left(A^n\right)_{21}$ – нижний элемент этого столбца, то есть элемент $\left(2, 1\right)$ матрицы $A^n$. Таким образом, всё свелось к вычислению $A^n$.

Пусть $n = 2^k$. Так как перемножаются степени одной матрицы, $A^i A^j = A^{i+j}$; в частности $\left(A^{2^s}\right)^2 = A^{2^s} A^{2^s} = A^{2^{s+1}}$. Поэтому, начиная с $A = A^{2^0}$, последовательными возведениями в квадрат получаем

$$A^{2^0}\ \xrightarrow{\left(\,\cdot\,\right)^2} \ A^{2^1} \xrightarrow{\left(\,\cdot\,\right)^2} \ A^{2^2} \xrightarrow{\left(\,\cdot\,\right)^2} \ \ldots \ \xrightarrow{\left(\,\cdot\,\right)^2} A^{2^k}.$$

Переходов от показателя $2^0$ до $2^k$ ровно $k$, и каждый – одно матричное умножение. Итого $k$ умножений матриц $2 \times 2$, и матрица $A^n = A^{2^k}$ готова. Фазы сборки слагаемых показателя на этом пути не возникает.

Подсчитаем количество арифметических операций. Одно умножение матриц $2 \times 2$ – это $8$ умножений и $4$ сложения чисел, всего $12$ операций. Значит, всё вычисление стоит

$$\underbrace{k}_\text{возведений в квадрат} \cdot \underbrace{12}_{8+4} = 12k$$

операций. Это линейно по $k$, то есть $O(k)$. А $n = 2^k$ по определению логарифма означает $k = \log_2 n,$ поэтому

$$12k = O(k) = O(\log_2 n).$$

$\square$