Быстрое вычисление членов линейной рекуррентной последовательности — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 21: Строка 21:
 
\end{pmatrix}</tex>
 
\end{pmatrix}</tex>
  
Заметим, что умножив <tex>A_0</tex> слева на <tex>T</tex> мы получим столбик <tex>A_1</tex> следующего вида:  
+
Заметим, что умножив <tex>A_0</tex> слева на <tex>T</tex>, мы получим столбик <tex>A_1</tex> следующего вида:  
 
<tex>A_1 = T \cdot A_0 = \begin{pmatrix}
 
<tex>A_1 = T \cdot A_0 = \begin{pmatrix}
 
a_{k}\\
 
a_{k}\\
Строка 28: Строка 28:
 
a_1
 
a_1
 
\end{pmatrix}</tex>
 
\end{pmatrix}</tex>
Аналогично домножив <tex>A_1</tex> слева на <tex>T</tex> получим  
+
Аналогично, домножив <tex>A_1</tex> слева на <tex>T</tex>, получим  
 
<tex>A_2 = T \cdot A_1 = \begin{pmatrix}
 
<tex>A_2 = T \cdot A_1 = \begin{pmatrix}
 
a_{k + 1}\\
 
a_{k + 1}\\
Строка 36: Строка 36:
 
\end{pmatrix}</tex>
 
\end{pmatrix}</tex>
  
Продолжая так для любого <tex>i</tex> мы получим столбик <tex>A_i</tex> состоящий из <tex>k</tex> подряд идущий членов последовательности, начиная с <tex>a_i</tex>
+
Продолжая так для любого <tex>i</tex>, мы получим столбик <tex>A_i</tex>, состоящий из <tex>k</tex> подряд идущий членов последовательности, начиная с <tex>a_i</tex>

Версия 18:07, 11 июня 2018

Пусть нам дана линейная реккурента размера [math]k[/math]. А именно: [math]a_n = c_1 \cdot a_{n - 1} + c_2 \cdot a_{n - 2} + \cdots + c_k \cdot a_{n - k}[/math], а так же заданы [math]k[/math] первых членов. Требуется уметь вычислять произвольное [math]a_n[/math].

Самый простой способ сделать это — последовательно считать каждый [math]a_i[/math], пока [math]i[/math] не сравняется с [math]n[/math]. Однако этот способ не самый эффективный, ведь он, очевидно, требует [math]O(n \cdot k)[/math] времени. Хочется уметь как-то быстрее решать эту задачу. Рассмотрим два способа это сделать.

Первый способ (за [math]O(k^3 \cdot logn)[/math])

Заметим, что линейные рекурренты хорошо выражаются через матрицы. Запишем наши первые [math]k[/math] членов последовательности в столбик. [math]A_0 = \begin{pmatrix} a_{k - 1}\\ a_{k - 2}\\ \vdots \\ a_0 \end{pmatrix}[/math] Так же выпишем следующую матрицу перехода: [math]T = \begin{pmatrix} c_1 & c_2 & c_3 & \cdots & c_k\\ 1 & 0 & 0 & \cdots & 0\\ 0 & 1 & 0 & \cdots & 0\\ \vdots & \vdots & \vdots & ~ & \vdots \\ 0 & 0 & 0 & \cdots & 1\\ \end{pmatrix}[/math]

Заметим, что умножив [math]A_0[/math] слева на [math]T[/math], мы получим столбик [math]A_1[/math] следующего вида: [math]A_1 = T \cdot A_0 = \begin{pmatrix} a_{k}\\ a_{k - 1}\\ \vdots \\ a_1 \end{pmatrix}[/math] Аналогично, домножив [math]A_1[/math] слева на [math]T[/math], получим [math]A_2 = T \cdot A_1 = \begin{pmatrix} a_{k + 1}\\ a_{k}\\ \vdots \\ a_2 \end{pmatrix}[/math]

Продолжая так для любого [math]i[/math], мы получим столбик [math]A_i[/math], состоящий из [math]k[/math] подряд идущий членов последовательности, начиная с [math]a_i[/math]