Рекурсивная процедура вычисления многочлена
Как разбить вычисление многочлена на две подзадачи равного размера? Вос- пользуемся полезным приемом: определим два многочлена Aeven(x) и AoЛ(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) нашей структуры алгоритма.
Еще по теме Рекурсивная процедура вычисления многочлена:
- Вычисление символических дирекций
- ВЫЧИСЛЕНИЕ СРОКА СТАБИЛЬНОСТИ БРАКА
- Вычисление ошибки выборки.
- Вычисление ошибки выборки.
- Вычисление ошибки выборки.
- Вычисление местного звездного времени
- Статья 676. Вычисление гарантийного срока
- Статья 860. Порядок вычисления гарантийного срока
- Вычисление ошибки репрезентативности для собственно случайной выборки.
- Схема «Процедуры комфортизации».
- Схема «Процедуры комфортизации».
- 3. Процедуры банкротства гражданина
- ИТАК, ПРОЦЕДУРА КОМФОРТИЗАЦИИ.
- ИТАК, ПРОЦЕДУРА КОМФОРТИЗАЦИИ.
- 28. Процедура наблюдения
- ПРОЦЕДУРЫ И РИТУАЛЫ