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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 3: Строка 3:
 
Самый простой способ сделать это {{---}} последовательно считать каждый <tex>a_i</tex>,  пока <tex>i</tex> не сравняется с <tex>n</tex>. Однако этот способ не самый эффективный, ведь он, очевидно, требует <tex>O(n \cdot k)</tex> времени. Хочется уметь как-то быстрее решать эту задачу. Рассмотрим два способа это сделать.
 
Самый простой способ сделать это {{---}} последовательно считать каждый <tex>a_i</tex>,  пока <tex>i</tex> не сравняется с <tex>n</tex>. Однако этот способ не самый эффективный, ведь он, очевидно, требует <tex>O(n \cdot k)</tex> времени. Хочется уметь как-то быстрее решать эту задачу. Рассмотрим два способа это сделать.
  
== Первый способ (за <tex>O(k^3 \cdot logn)</tex>) ==
+
== Умножение матриц (за <tex>O(k^3 \cdot logn)</tex>) ==
  
 
Заметим, что линейные рекурренты хорошо выражаются через матрицы. Запишем наши первые <tex>k</tex> членов последовательности в столбик.  
 
Заметим, что линейные рекурренты хорошо выражаются через матрицы. Запишем наши первые <tex>k</tex> членов последовательности в столбик.  
Строка 43: Строка 43:
  
 
Используя быстрое возведения в степень второй пункт будет тратить <tex>O(k^3 \cdot logn)</tex> времени, умножение же в третьем пункте выполняется за <tex>O(k^2)</tex>. Итого мы получили алгоритм за <tex>O(k^3 \cdot logn)</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>) ==
 +
 +
Вспомним, что по [[Теорема о связи между рациональностью производящей функции и линейной рекуррентностью задаваемой ей последовательности|теореме о связи рекурренты и многочленов]] наша реккурента эквивалента некому многочлену <tex>A(t) = \dfrac{P(t)}{Q(t)}</tex>, при это <tex>Q(t) = 1 - c_1 \cdot t - c_2 \cdot t^2 - \cdots - c_k \cdot t^k</tex>. Домножим числитель и знаменатель на <tex>Q(-t)</tex>. Новый знаменатель <tex>R(t) = Q(t) \cdot Q(-t)</tex>. При этом <tex>r_n = \sum\limits_{i = 0}^{n} q_i \cdot q_{n - i} \cdot (-1)^{n - i}</tex>

Версия 19:40, 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]. Пользуясь ассоциативность произведения матриц, можно записать, что [math]A_i = T^i \cdot A_0[/math]. Из этого соотношения вытекает алгоритм вычисления произвольного [math]a_n[/math]:

  1. Инициализировать матрицы [math]A_0[/math] и [math]T[/math]
  2. Возвести матрицу [math]T[/math] в степень [math]n[/math]
  3. Посчитать [math]A_n[/math] как [math]T^n \cdot A_0[/math] и взять из него [math]a_n[/math]

Используя быстрое возведения в степень второй пункт будет тратить [math]O(k^3 \cdot logn)[/math] времени, умножение же в третьем пункте выполняется за [math]O(k^2)[/math]. Итого мы получили алгоритм за [math]O(k^3 \cdot logn)[/math].

Связь с многочленами (за [math]O(k^2 \cdot logn)[/math])

Вспомним, что по теореме о связи рекурренты и многочленов наша реккурента эквивалента некому многочлену [math]A(t) = \dfrac{P(t)}{Q(t)}[/math], при это [math]Q(t) = 1 - c_1 \cdot t - c_2 \cdot t^2 - \cdots - c_k \cdot t^k[/math]. Домножим числитель и знаменатель на [math]Q(-t)[/math]. Новый знаменатель [math]R(t) = Q(t) \cdot Q(-t)[/math]. При этом [math]r_n = \sum\limits_{i = 0}^{n} q_i \cdot q_{n - i} \cdot (-1)^{n - i}[/math]