Рекурсивная процедура вычисления многочлена

Мы хотим создать алгоритм рекурсивного вычисления A для каждого из корней (2n)-й степени из единицы, чтобы воспользоваться знакомым рекуррентным отно- шением из (5.1), а именно T(n) < 2T(n/2) + O(n), где T(n) в данном случае обозна- чает количество операций, необходимых для вычисления многочлена степени n - 1 для всех корней (2n)-й степени из единицы.
Для простоты при описании алгоритма будем считать, что n является степенью 2.

Как разбить вычисление многочлена на две подзадачи равного размера? Вос- пользуемся полезным приемом: определим два многочлена Aeven(x) и A(x), состо- ящих из четных и нечетных коэффициентов A соответственно. То есть

и

Простые алгебраические выкладки показывают, что

Итак, в нашем распоряжении появился способ вычисления A(x) с постоянным количеством операций через вычисление двух многочленов, степень каждого из которых равна половине степени A.

Теперь предположим, что каждый из многочленов Aeven и Aodd вычисляется для корней n-й степени из единицы. Эта задача в точности соответствует той, с кото- рой мы сталкиваемся для A и корней (2n)-й степени из единицы, за исключением того, что входные данные уменьшились вдвое: степень равна (n - 2)/2 вместо n - 1, а вместо 2n используются n корней. Следовательно, эти вычисления могут выполняться за время T(n/2) для каждого из многочленов Aeven и AoJd, с суммарным временем 2T(n/2).

Мы очень близко подошли к созданию рекурсивного алгоритма, который удов- летворяет условию (5.1) и обеспечивает желаемое время выполнения; остается лишь произвести вычисления A для корней (2n)-й степени из единицы с исполь- зованием O(n) дополнительных операций. Но с учетом результатов рекурсивных вызовов для.4eveя iь4oiMэтo несложно. Рассмотрим один из этих корней из единицы co/⅛ = Величина j равна (e⅝'/&)2 = а следовательно, ⅜>Jlп является

корнем n-й степени из единицы. Таким образом, когда мы переходим к вычисле- ниям

выясняется, что оба вычисления в правой части были выполнены на шаге ре- курсии и A(цc2n) можно определить с постоянным количеством операций. Таким образом, выполнение этих операций для всех 2n корней из единицы означает O(n) дополнительных операций после двух рекурсивных вызовов, а следователь- но, граница T(n) количества операций в самом деле удовлетворяет отношению T(n) < 2T(n/2) + O(n). Та же процедура применяется для вычисления многочлена B для корней (2n)-й степени из единицы, и это дает желаемую границу O(n log n) для шага (i) нашей структуры алгоритма.

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

Еще по теме Рекурсивная процедура вычисления многочлена:

  1. Вычисление символических дирекций
  2. ВЫЧИСЛЕНИЕ СРОКА СТАБИЛЬНОСТИ БРАКА
  3. Вычисление ошибки выборки.
  4. Вычисление ошибки выборки.
  5. Вычисление ошибки выборки.
  6. Вычисление местного звездного времени
  7. Статья 676. Вычисление гарантийного срока
  8. Статья 860. Порядок вычисления гарантийного срока
  9. Вычисление ошибки репрезентативности для собственно случайной выборки.
  10. Схема «Процедуры комфортизации».
  11. Схема «Процедуры комфортизации».
  12. 3. Процедуры банкротства гражданина
  13. ИТАК, ПРОЦЕДУРА КОМФОРТИЗАЦИИ.
  14. ИТАК, ПРОЦЕДУРА КОМФОРТИЗАЦИИ.
  15. 28. Процедура наблюдения
  16. ПРОЦЕДУРЫ И РИТУАЛЫ