English
!

Архив публикаций

Тезисы

XXIII-ая конференция

Исследование алгоритма декомпозиции полиномов, основанного на разбиениях

Перминова М.Ю.

ТУСУР, Россия, 634050, Томск, пр. Ленина 40, mary42rus@gmail.com

1  стр. (принято к публикации)

Задача представления полинома $F(x)$ в виде композиции двух полиномов $B\bigl(A(x)\bigr)$ имеет множество решений. Для её решения был предложен новый алгоритм \cite{algorithm}, основанный на генерации разбиений \cite{partition}.

Определим вычислительную сложность $z(n)$ данного алгоритма. В соответствии с алгоритмом для каждого уравнения из списка $T$ генерируется список разбиений $P$, по $P$ получается список мономов $M$. Далее из мономов составляется уравнение $Eq$ и находится его решение $S$.

Таким образом, $z(n)$ состоит из нескольких частей:

1. Временная сложность генерации разбиений $z_1=3\begin{vmatrix}n\\m,s \end{vmatrix} + s$, где $m$ и $s$ --- степени полиномов $A(x)$ и $B(x)$ соответственно; $n$ --- натуральное число, для которого находятся все разбиения.

2. Временная сложность получения монома $z_2=s\begin{vmatrix}n\\m,s \end{vmatrix}$.

3. Временная сложность решения уравнения $z_3=\cfrac{(m+s-1)(m+s)}{2}$.

Таким образом, временная сложность в п. 1 и п. 2 рассмотрена только для одного уравнения. Учитывая временную сложность для всех уравнений, число которых равняется $m+s-1$, получим $z(m,s)$: $$ z(m,s)=z_1+z_2+z_3 =\sum_{j=1}^{m+s-1} \left(3\begin{vmatrix}n\\m,s \end{vmatrix} + s + s\begin{vmatrix}n\\m,s \end{vmatrix}\right) + \cfrac{(m+s-1)(m+s)}{2}. $$

После преобразования данного выражения и введения различных допущений получим вычислительную сложность $z(m,s)$ порядка $n^2$. Анализ показал, что большинство алгоритмов декомпозиции полиномов имеют вычислительную сложность такого же порядка.

\begin{thebibliography}{100} \bibitem{algorithm} \textit{Перминова М. Ю.}, \textit{Кручинин В. В.} Алгоритм декомпозиции полиномов, основанный на разбиениях // Доклады Томского государственного университета систем управления и радиоэлектроники. \textnumero 3(37), 2015 (в печати). \bibitem{partition} \textit{Перминова М. Ю.}, \textit{Кручинин В. В.} Алгоритмы рекурсивной генерации ограниченных разбиений натурального числа // Доклады Томского государственного университета систем управления и радиоэлектроники. \textnumero 4(34), 2014. Стр. 89-94. \end{thebibliography}



© 2004 Дизайн Лицея Информационных технологий №1533