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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Связь с многочленами (за O(k^2 \cdot logn)))
(Связь с многочленами (за O(k^2 \cdot \log n)))
(не показаны 22 промежуточные версии этого же участника)
Строка 1: Строка 1:
Пусть нам дана [[Теорема о связи между рациональностью производящей функции и линейной рекуррентностью задаваемой ей последовательности#def_linear.|линейная реккурента]] размера <tex>k</tex>. А именно: <tex>a_n = c_1 \cdot a_{n - 1} + c_2 \cdot a_{n - 2} + \cdots + c_k \cdot a_{n - k}</tex>, а так же заданы <tex>k</tex> первых членов последовательности. Требуется уметь вычислять произвольное <tex>a_n</tex>.
+
Пусть нам дана [[Теорема о связи между рациональностью производящей функции и линейной рекуррентностью задаваемой ей последовательности#def_linear.|линейная рекуррентная последовательность]](далее ЛРП) порядка <tex>k</tex>. А именно: <tex>a_n = c_1 \cdot a_{n - 1} + c_2 \cdot a_{n - 2} + \cdots + c_k \cdot a_{n - k}</tex> при <tex>n \geqslant k</tex>, а так же заданы <tex>k</tex> первых членов последовательности. Требуется уметь вычислять произвольное <tex>a_n</tex>.
  
Самый простой способ сделать это {{---}} последовательно считать каждый <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 \log n)</tex>) ==
  
Заметим, что линейные рекурренты хорошо выражаются через матрицы. Запишем наши первые <tex>k</tex> членов последовательности в столбик.  
+
Заметим, что ЛРП хорошо выражаются через матрицы. Запишем наши первые <tex>k</tex> членов последовательности в столбик.  
 
<tex>A_0 = \begin{pmatrix}
 
<tex>A_0 = \begin{pmatrix}
 
a_{k - 1}\\
 
a_{k - 1}\\
Строка 21: Строка 21:
 
\end{pmatrix}</tex>
 
\end{pmatrix}</tex>
  
Заметим, что умножив <tex>A_0</tex> слева на <tex>T</tex>, мы получим столбик <tex>A_1</tex> следующего вида:  
+
Заметим, что умножив <tex>T</tex> на <tex>A_0</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>T</tex> на <tex>A_1</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>A_i = T^i \cdot A_0</tex>. Из этого соотношения вытекает алгоритм вычисления произвольного <tex>a_n</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_0</tex> и <tex>T</tex>
Строка 42: Строка 42:
 
# Посчитать <tex>A_n</tex> как <tex>T^n \cdot A_0</tex> и взять из него <tex>a_n</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 \log n)</tex> времени. Умножение же в третьем пункте выполняется за <tex>O(k^2)</tex>.
  
Итого мы получили алгоритм за <tex>O(k^3 \cdot logn)</tex>.
+
Итого мы получили алгоритм, работающий за <tex>O(k^3 \cdot \log n)</tex>.
  
== Связь с многочленами (за <tex>O(k^2 \cdot logn)</tex>) ==
+
== Связь с многочленами (за <tex>O(k^2 \cdot \log n)</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>. Нетрудно заметить, что при нечётных <tex>n</tex> коэффициенты <tex>r_n</tex> обращаются в <tex>0</tex>, a <tex>r_0 = 1</tex>.
+
Вспомним, что по [[Теорема о связи между рациональностью производящей функции и линейной рекуррентностью задаваемой ей последовательности|теореме о связи ЛРП и многочленов]] наша ЛРП эквивалента некому отношению многочленов <tex>A(t) = \dfrac{P(t)}{Q(t)}</tex>, при этом <tex>Q(t) = q_0 + q_1 \cdot t + \cdots q_k \cdot t^k = 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>. Нетрудно заметить, что при нечётных <tex>n</tex> коэффициенты <tex>r_n</tex> обращаются в <tex>0</tex>, a <tex>r_0 = 1</tex>.
  
Отсюда мы получаем, что многочлен <tex>R(t)</tex> имеет вид: <tex>R(t) = 1 + r_2 \cdot t^2 + r_4 \cdot t^4 + \cdots + r_{2k} \cdot t^{2k}</tex>. Однако вспомним о связи с рекуррентой, а именно мы получили, что <tex>a_n = -r_2 \cdot a_{n - 2} - r_4 \cdot a_{n - 4} - \cdots - r_{2k} \cdot a_{n - 2k}</tex>
+
Отсюда мы получаем, что многочлен <tex>R(t)</tex> имеет вид: <tex>R(t) = 1 + r_2 \cdot t^2 + r_4 \cdot t^4 + \cdots + r_{2k} \cdot t^{2k}</tex>. Однако вспомним о связи с ЛРП, тогда мы получили, что <tex>a_n = -r_2 \cdot a_{n - 2} - r_4 \cdot a_{n - 4} - \cdots - r_{2k} \cdot a_{n - 2k}</tex>
  
 
Иными словами мы получили новое рекуррентное соотношение для данной последовательности, где каждый элемент зависит от элементов с номерами, имеющими такую же чётность, что номер исходного. То есть по сути наша последовательность разделилась на две независимых: с чётными и нечётными номерами. Можно сказать, что мы теперь ищем не <tex>a_n</tex> из исходной последовательности, а <tex>a'_{n~div~2}</tex> из подпоследовательности элементов c номерами, имеющими ту же чётность, что и <tex>n</tex>. Заметим, что этот процесс можно проделывать далее пока <tex>n \geqslant k</tex>, ведь в итоге искомый элемент окажется среди <tex>k</tex> первых. Всё, что нам нужно,{{---}} поддерживать первые <tex>k</tex> элементов для каждой новой последовательности.
 
Иными словами мы получили новое рекуррентное соотношение для данной последовательности, где каждый элемент зависит от элементов с номерами, имеющими такую же чётность, что номер исходного. То есть по сути наша последовательность разделилась на две независимых: с чётными и нечётными номерами. Можно сказать, что мы теперь ищем не <tex>a_n</tex> из исходной последовательности, а <tex>a'_{n~div~2}</tex> из подпоследовательности элементов c номерами, имеющими ту же чётность, что и <tex>n</tex>. Заметим, что этот процесс можно проделывать далее пока <tex>n \geqslant k</tex>, ведь в итоге искомый элемент окажется среди <tex>k</tex> первых. Всё, что нам нужно,{{---}} поддерживать первые <tex>k</tex> элементов для каждой новой последовательности.
Строка 56: Строка 56:
 
Исходя из всего вышесказанного получаем алгоритм:
 
Исходя из всего вышесказанного получаем алгоритм:
  
     get_nth(n, a[], <tex>Q</tex>) {
+
     get_nth(n, a[], <tex>Q</tex>)  
         '''while''' (n <tex>\geqslant</tex> k) {
+
         '''while''' n <tex>\geqslant</tex> k
             calculate a[k], a[k + 1], <tex>\cdots</tex>, a[2k - 1];
+
             '''for''' i = k '''to''' 2k - 1
             <tex>R = Q(t) \cdot Q(-t)</tex>;
+
                a[i] = <tex>\sum\limits_{j = 1}^{k}</tex> -q[j] <tex>\cdot</tex> a[i - j]
             leave a[i] with (i % 2 == n % 2);
+
             <tex>R = Q(t) \cdot Q(-t)</tex>
 +
             '''filter''' a[i] '''with''' (i '''mod''' 2 == n '''mod''' 2)
 
             <tex>Q = R(\sqrt{t})</tex>
 
             <tex>Q = R(\sqrt{t})</tex>
             n = n div 2;
+
             n = n '''div''' 2
        }
+
         '''return''' a[n]
         return a[n];
 
    }
 
  
Вычисление <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>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(\log n)</tex> в силу того, что мы делим <tex>n</tex> на <tex>2</tex> каждый раз.  
  
Итого мы получили алгоритм, работающий за <tex>O(k^2 \cdot logn)</tex>
+
Итого мы получили алгоритм, работающий за <tex>O(k^2 \cdot \log n)</tex>
  
 
==См. также==
 
==См. также==
 
* [[Теорема о связи между рациональностью производящей функции и линейной рекуррентностью задаваемой ей последовательности|Теорема о связи между рациональностью производящей функции и линейной рекуррентностью задаваемой ей последовательности]]
 
* [[Теорема о связи между рациональностью производящей функции и линейной рекуррентностью задаваемой ей последовательности|Теорема о связи между рациональностью производящей функции и линейной рекуррентностью задаваемой ей последовательности]]
 
* [[Производящая функция| Производящая функция]]
 
* [[Производящая функция| Производящая функция]]
 +
 +
== Источники информации ==
 +
* [https://studfiles.net/preview/5826382/page:21/ Вычисление ЛРП с помощью матриц]
  
  
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Производящие функции]]
 
[[Категория: Производящие функции]]

Версия 22:42, 14 июня 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]n \geqslant 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 \log n)[/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} & c_k\\ 1 & 0 & 0 & \cdots & 0 & 0\\ 0 & 1 & 0 & \cdots & 0 & 0\\ \vdots & \vdots & \vdots & ~ & \vdots & \vdots \\ 0 & 0 & 0 & \cdots & 1 & 0\\ \end{pmatrix}[/math]

Заметим, что умножив [math]T[/math] на [math]A_0[/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]T[/math] на [math]A_1[/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 \log n)[/math] времени. Умножение же в третьем пункте выполняется за [math]O(k^2)[/math].

Итого мы получили алгоритм, работающий за [math]O(k^3 \cdot \log n)[/math].

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

Вспомним, что по теореме о связи ЛРП и многочленов наша ЛРП эквивалента некому отношению многочленов [math]A(t) = \dfrac{P(t)}{Q(t)}[/math], при этом [math]Q(t) = q_0 + q_1 \cdot t + \cdots q_k \cdot t^k = 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]. Нетрудно заметить, что при нечётных [math]n[/math] коэффициенты [math]r_n[/math] обращаются в [math]0[/math], a [math]r_0 = 1[/math].

Отсюда мы получаем, что многочлен [math]R(t)[/math] имеет вид: [math]R(t) = 1 + r_2 \cdot t^2 + r_4 \cdot t^4 + \cdots + r_{2k} \cdot t^{2k}[/math]. Однако вспомним о связи с ЛРП, тогда мы получили, что [math]a_n = -r_2 \cdot a_{n - 2} - r_4 \cdot a_{n - 4} - \cdots - r_{2k} \cdot a_{n - 2k}[/math]

Иными словами мы получили новое рекуррентное соотношение для данной последовательности, где каждый элемент зависит от элементов с номерами, имеющими такую же чётность, что номер исходного. То есть по сути наша последовательность разделилась на две независимых: с чётными и нечётными номерами. Можно сказать, что мы теперь ищем не [math]a_n[/math] из исходной последовательности, а [math]a'_{n~div~2}[/math] из подпоследовательности элементов c номерами, имеющими ту же чётность, что и [math]n[/math]. Заметим, что этот процесс можно проделывать далее пока [math]n \geqslant k[/math], ведь в итоге искомый элемент окажется среди [math]k[/math] первых. Всё, что нам нужно,— поддерживать первые [math]k[/math] элементов для каждой новой последовательности.

Исходя из всего вышесказанного получаем алгоритм:

   get_nth(n, a[], [math]Q[/math]) 
       while n [math]\geqslant[/math] k
            for i = k to 2k - 1
                a[i] = [math]\sum\limits_{j = 1}^{k}[/math] -q[j] [math]\cdot[/math] a[i - j]
            [math]R = Q(t) \cdot Q(-t)[/math]
            filter a[i] with (i mod 2 == n mod 2)
            [math]Q = R(\sqrt{t})[/math]
            n = n div 2
       return a[n]

Вычисление [math]a[k], a[k + 1], \cdots , a[2k - 1][/math] занимает [math]O(k^2)[/math] времени, ибо их всего [math]k[/math], а каждый считается за [math]O(k)[/math]. Умножение многочленов длины порядка [math]k[/math] также занимает [math]O(k^2)[/math] времени. Итераций внешнего цикла будет [math]O(\log n)[/math] в силу того, что мы делим [math]n[/math] на [math]2[/math] каждый раз.

Итого мы получили алгоритм, работающий за [math]O(k^2 \cdot \log n)[/math]

См. также

Источники информации