Быстрое вычисление членов линейной рекуррентной последовательности — различия между версиями
Dogzik (обсуждение | вклад) |
м (rollbackEdits.php mass rollback) |
||
(не показано 38 промежуточных версий 2 участников) | |||
Строка 1: | Строка 1: | ||
− | Пусть нам дана [[Теорема о связи между рациональностью производящей функции и линейной рекуррентностью задаваемой ей последовательности#def_linear.|линейная | + | Пусть нам дана [[Теорема о связи между рациональностью производящей функции и линейной рекуррентностью задаваемой ей последовательности#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>a_i</tex>, пока <tex>i</tex> не станет равен <tex>n</tex>. Однако этот способ не самый эффективный, он, очевидно, требует <tex>O(n \cdot k)</tex> времени, но можно сделать это быстрее. Рассмотрим два способа это сделать. |
− | == | + | == Умножение матриц (за <tex>O(k^3 \cdot \log n)</tex>) == |
− | Заметим, что | + | Заметим, что ЛРП хорошо выражаются через матрицы. Запишем наши первые <tex>k</tex> членов последовательности в столбик. |
<tex>A_0 = \begin{pmatrix} | <tex>A_0 = \begin{pmatrix} | ||
a_{k - 1}\\ | a_{k - 1}\\ | ||
Строка 14: | Строка 14: | ||
Так же выпишем следующую матрицу перехода: | Так же выпишем следующую матрицу перехода: | ||
<tex>T = \begin{pmatrix} | <tex>T = \begin{pmatrix} | ||
− | c_1 & c_2 & c_3 & \cdots & c_k\\ | + | c_1 & c_2 & c_3 & \cdots & c_{k - 1} & c_k\\ |
− | 1 & 0 & 0 & \cdots & 0\\ | + | 1 & 0 & 0 & \cdots & 0 & 0\\ |
− | 0 & 1 & 0 & \cdots & 0\\ | + | 0 & 1 & 0 & \cdots & 0 & 0\\ |
− | \vdots & \vdots & \vdots & ~ & \vdots \\ | + | \vdots & \vdots & \vdots & ~ & \vdots & \vdots \\ |
− | 0 & 0 & 0 & \cdots & 1\\ | + | 0 & 0 & 0 & \cdots & 1 & 0\\ |
\end{pmatrix}</tex> | \end{pmatrix}</tex> | ||
− | Заметим, что умножив <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> | + | Аналогично, домножив <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>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 \log n)</tex> времени. Умножение же в третьем пункте выполняется за <tex>O(k^2)</tex>. |
+ | |||
+ | Итого мы получили алгоритм, работающий за <tex>O(k^3 \cdot \log n)</tex>. | ||
+ | |||
+ | == Связь с многочленами (за <tex>O(k^2 \cdot \log n)</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>a_n</tex> из исходной последовательности, а <tex>a'_{n~div~2}</tex> из подпоследовательности элементов c номерами, имеющими ту же чётность, что и <tex>n</tex>. Заметим, что этот процесс можно проделывать далее пока <tex>n \geqslant k</tex>, ведь в итоге искомый элемент окажется среди <tex>k</tex> первых. Всё, что нам нужно,{{---}} поддерживать первые <tex>k</tex> элементов для каждой новой последовательности. | ||
+ | |||
+ | Исходя из всего вышесказанного получаем алгоритм: | ||
+ | |||
+ | get_nth(n, a[], <tex>Q</tex>) | ||
+ | '''while''' n <tex>\geqslant</tex> k | ||
+ | '''for''' i = k '''to''' 2k - 1 | ||
+ | a[i] = <tex>\sum\limits_{j = 1}^{k}</tex> -q[j] <tex>\cdot</tex> a[i - j] | ||
+ | <tex>R = Q(t) \cdot Q(-t)</tex> | ||
+ | '''filter''' a[i] '''with''' (i '''mod''' 2 == n '''mod''' 2) | ||
+ | <tex>Q = R(\sqrt{t})</tex> | ||
+ | n = n '''div''' 2 | ||
+ | '''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(\log n)</tex> в силу того, что мы делим <tex>n</tex> на <tex>2</tex> каждый раз. | ||
+ | |||
+ | Итого мы получили алгоритм, работающий за <tex>O(k^2 \cdot \log n)</tex> | ||
+ | |||
+ | ==См. также== | ||
+ | * [[Теорема о связи между рациональностью производящей функции и линейной рекуррентностью задаваемой ей последовательности|Теорема о связи между рациональностью производящей функции и линейной рекуррентностью задаваемой ей последовательности]] | ||
+ | * [[Производящая функция| Производящая функция]] | ||
+ | |||
+ | == Источники информации == | ||
+ | * [https://studfiles.net/preview/5826382/page:21/ Вычисление ЛРП с помощью матриц] | ||
+ | |||
+ | |||
+ | [[Категория: Дискретная математика и алгоритмы]] | ||
+ | [[Категория: Производящие функции]] |
Текущая версия на 19:11, 4 сентября 2022
Пусть нам дана линейная рекуррентная последовательность(далее ЛРП) порядка . А именно: при , а так же заданы первых членов последовательности. Требуется уметь вычислять произвольное .
Самый простой способ сделать это — последовательно считать каждый
, пока не станет равен . Однако этот способ не самый эффективный, он, очевидно, требует времени, но можно сделать это быстрее. Рассмотрим два способа это сделать.Умножение матриц (за )
Заметим, что ЛРП хорошо выражаются через матрицы. Запишем наши первые
членов последовательности в столбик. Так же выпишем следующую матрицу перехода:Заметим, что умножив
на , мы получим столбик следующего вида: Аналогично, домножив на , получимПродолжая так, для любого целого неотрицательного
, мы получим столбик , состоящий из подряд идущих членов последовательности, начиная с . Пользуясь ассоциативностью произведения матриц, можно записать, что . Из этого соотношения вытекает алгоритм вычисления произвольного :- Инициализировать матрицы и
- Возвести матрицу в степень
- Посчитать как и взять из него
Используя быстрое возведение в степень во втором пункте, мы будем тратить
времени. Умножение же в третьем пункте выполняется за .Итого мы получили алгоритм, работающий за
.Связь с многочленами (за )
Вспомним, что по теореме о связи ЛРП и многочленов наша ЛРП эквивалента некому отношению многочленов , при этом . Домножим числитель и знаменатель на . Новый знаменатель . При этом . Нетрудно заметить, что при нечётных коэффициенты обращаются в , a .
Отсюда мы получаем, что многочлен
имеет вид: . Однако вспомним о связи с ЛРП, тогда мы получили, чтоИными словами мы получили новое рекуррентное соотношение для данной последовательности, где каждый элемент зависит от элементов с номерами, имеющими такую же чётность, что номер исходного. То есть по сути наша последовательность разделилась на две независимых: с чётными и нечётными номерами. Можно сказать, что мы теперь ищем не
из исходной последовательности, а из подпоследовательности элементов c номерами, имеющими ту же чётность, что и . Заметим, что этот процесс можно проделывать далее пока , ведь в итоге искомый элемент окажется среди первых. Всё, что нам нужно,— поддерживать первые элементов для каждой новой последовательности.Исходя из всего вышесказанного получаем алгоритм:
get_nth(n, a[],) while n k for i = k to 2k - 1 a[i] = -q[j] a[i - j] filter a[i] with (i mod 2 == n mod 2) n = n div 2 return a[n]
Вычисление
занимает времени, ибо их всего , а каждый считается за . Умножение многочленов длины порядка также занимает времени. Итераций внешнего цикла будет в силу того, что мы делим на каждый раз.Итого мы получили алгоритм, работающий за