Предположим, что нам нужно вычислить полином

\[A(x) = \sum\limits_{j=0}^{n-1} a_{i}x^j\]

с границей степени \(n\) в некоторой точке \(x\).

Полином можно записать в виде:

\[ A(x) = a_{n-1}x^{n-1} + a_{n-2}x^{n-2} + \dots + a_1x + a_0 \]

Если последовательно выносить за скобки \(x\), то мы будем получать полиномы с уменьшающимися степенями. В итоге, полином \(A(x)\) будет представлен в следующем виде:

\[ A(x) = (( \dots (a_{n-1}x + a_{n-2}) + \dots + a_2)x + a_1)x + a_0 \]

Такое представление позволяет эффективно выполнить операцию вычисления полинома за время \(\Theta (n)\) и называется схемой Горнера.

Мы можем составить вектор коэффициентов \(a = (a_0, a_1, \dots, a_{n-1})\), тем самым получив основанное на коэффициентах представление полинома.

Рассмотрим пример.

Вычислите полином \(A(x) = 6x^5-2x^3+x^2-10x+13\) в точке \(x=2\).

Для наглядности представим решение в виде таблицы из двух строк.

Коэффициенты 6 0 -2 1 -10 13
\(\small x = 2\) \(\small 6\) \(\small 6*2+0=12\) \(\small 12*2-2=22\) \(\small 22*2+1=45\) \(\small 45*2-10=80\) \(\small 80*2+13=173\)

В колонках первой строки написаны числа из вектора коэффициентов. В колонках второй строки — вычисления для каждого из коэффициентов. Ответом является значение в последнем столбце второй строки.

Видим, что общее количество умножений равно количеству умножений для вычисления одной только высшей степени у первого одночлена \((6x^5)\) обычным методом грубой силы.

При этом не стоит забывать, что чем меньше количество одночленов и чем больше при этом степень полинома, тем менее эффективной становится такая схема расчетов.

Например, вычислим полином \(6x^5\) в точке \(x=2\):

Коэффициенты 6 0 0 0 0 0
\(\small x = 2\) \(\small 6\) \(\small 6*2+0=12\) \(\small 12*2+0=24\) \(\small 24*2+0=48\) \(\small 48*2+0=96\) \(\small 96*2+0=192\)

Мало того, что мы получили обычный алгоритм грубой силы, так еще и с ненужными добавлениями нуля на каждом шаге.