суми, далі твори і т.д. Метод Горнера вимагає не більше N операцій множення і N операцій додавання. p> Приклад: нехай дано поліном p (z) ступеня
N = 4: p (z) = 4z4 - 2z3 + 3z2 + z - 5.
P (z) = (4z3 - 2z2 + 3z + 1) z - 5 = ((4z2 - 2z + 3) z + 1) z - 5 = (((4z - 2) z +
+ 3) z + 1) z - 5.
Нехай
z = -1: 4 В· z = 4 В· (-1) = -4, -4 - 2 = -6, -6 В· z = -6 В· (-1) = 6, 6 + 3 = 9 , 9 В· z = 9 В· (-1)
= -9, -9 + 1 = -8, -8 В· z == -8 В· (-1) = 8, 8 - 5 = 3.
Мультиплікативна складність = 4, адитивна = 4. Якби поліном вважався прямо, то мультиплікативна складність склала б 6 операцій. p align="justify"> Обчислення полінома в точках за допомогою алгоритму В«розділяй і володарюйВ»:
Нехай необхідно обчислити поліном в декількох точках а 1 , а 2 , ..., а k , k? N. Покладемо спочатку
z = a 1 . Тоді можна записати
p (z) = (z - a 1 ) q (z) + r (z),
де q (z) і r (z) - приватне і залишок від ділення p (z) на (z - a 1 ). Цей результат можна поширити на більше число точок. Розглянемо твір і запишемо p (z) = m (z) q (z) + r (z). У точці z = a i поліном m (z) дорівнює нулю, тому p (a i ) = r (a i ). Тепер обчислення полінома p (z) звелося до обчислення полінома r (z), ступінь якого менше.
Цей підхід можна використовувати для побудови алгоритму обчислення полінома ступеня N - 1 в N точках. Покладемо N = 2 l . Розділимо N точок на дві половини і утворюємо поліноми
і .
Розділимо p (z) на m 1 (z) і m 2 (z). При цьому отримаємо залишки r 1 (z) і r 2 (z) ступеня N/2. Тепер залишилося обчислити ці залишки в N/2 точках. Для обчислення залишків можна скористатися аналогічним прийомом, повторюючи його багато разів.
Приклад: Нехай потрібно обчислити поліном
p...
