89
правок
Изменения
Нет описания правки
\end{pmatrix}</tex>
Продолжая так для любого <tex>i</tex>, мы получим столбик <tex>A_i</tex>, состоящий из <tex>k</tex> подряд идущий членов последовательности, начиная с <tex>a_i</tex>. Пользуясь ассоциативность ассоциативностью произведения матриц, можно записать, что <tex>A_i = T^i \cdot A_0</tex>. Из этого соотношения вытекает алгоритм вычисления произвольного <tex>a_n</tex>:
# Инициализировать матрицы <tex>A_0</tex> и <tex>T</tex>
# Посчитать <tex>A_n</tex> как <tex>T^n \cdot A_0</tex> и взять из него <tex>a_n</tex>
Используя быстрое возведения возведение в степень , второй пункт будет тратить <tex>O(k^3 \cdot logn)</tex> времени, умножение же в третьем пункте выполняется за <tex>O(k^2)</tex>. Итого мы получили алгоритм за <tex>O(k^3 \cdot logn)</tex>.
== Связь с многочленами (за <tex>O(k^2 \cdot logn)</tex>) ==
</code>
Вычисление <tex>a[k], a[k + 1], \cdots , a[2k - 1]</tex> занимает <tex>O(k^2)</tex> времени, ибо их всего <tex>k</tex>, а каждое считается за <tex>O(k)</tex>. Умножение многочленов длины порядка <tex>k</tex> также занимает <tex>O(k^2)</tex> времени. Итераций внешнего цикла будет <tex>O(logn)</tex> в силу того, что мы делим <tex>n</tex> на <tex>2</tex> каждый раз. Итого мы получили алгоритм, работающий за <tex>O(k^2 \cdot logn)</tex>
