LINUX.ORG.RU
Форум — Development  

быстрое умножение многочленов


0

0

Как быстро перемножить два многочлена, заданных своими коэфициентами? Т.е. сложность должна быть не n^2, как при обычном умножении, а n*log(n). Интересует именно сам алгоритм, желательно без использования комплексных чисел.

★★★

там на быстрое дискретное преобразование фурье завязано. Тут можно почитать: Ноден, Китте: Алгебраическая Алгоритмика

dilmah ★★★★★
()

Есть очень простой алгоритм, который придумал Карацуба, кажется O(n^(log3/log2)). А вот O(nlog(n)) нет, самый быстрый вроде Schonhage-Strassen - O(nlog(n)log(log(n))), с FFT, описан во 2-м томе Искусстве Программирования.

grob ★★★★★
()
Ответ на: комментарий от grob

Спасибо, именно это мне и было нужно!

kmeaw ★★★
() автор топика
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.
Development