На этом шаге мы рассмотрим рекурсивную реализацию этой схемы.

Цель этой задачи - вычислить полином степени n:

    P(x) = c_nxⁿ + c_n-1x^n-1 + ... + c₁x + c₀   (4.5)

для некоторого вещественного значения x. Сумма состоит из степеней х, умноженных на коэффициенты с_i. Простейший алгоритм, вычисляющий каждую степень отдельно, потребовал бы порядка n² умножений. Тогда как схема Горнера позволяет сократить число умножений до n. Её идея - представить полином в виде:

    P(x) = с₀ + x(c₁ + x(c₂ + ... + x(c_n-1 + c_nx))).

Ясно, что размер задачи - это степень n полинома. Таким образом, начальное условие выполняется при n = 0 с очевидным результатом 0. На практике коэффициенты c должны быть определяющим полином списком (или похожей структурой данных вроде массива) из n + 1 элементов. Поэтому начальное условие достигается, когда длина этого списка равна 1.

Чтобы воспользоваться рекурсией, нужно найти подзадачу меньшего размера, подобную исходной. Декомпозиция задачи с уменьшением ее размера на 1:

                         _{полная задача
           ┎---------------------------------------------┑}
    P(x) = с₀ + x(c₁ + x(c₂ + ... + x(c_n-1 + c_nx))).
               ^{┕---------------------------------------┙
                              подзадача}

Если пренебречь коэффициентом c₀ и первым умножением на x, то получающаяся подзадача имеет точно такую же структуру, как у исходной задачи. Если p(c, x) - функция, вычисляющая заданный своими коэффициентами c полином от x, то рекурсивная формула будет такой:

    p(c, x) = c₀ + x * p(c_1...n, x),

где список c_1...n - это тот же список c без первого элемента. Полная рекурсивная функция будет такой:

               c₀,                   если n = 1,
    p(c, x) = 
               с₀ + х * p(c_1...n, х), если n > 1,

а соответствующий ей код приведён в примере 4.15.

Пример 4.15. Вычисление полинома по схеме Горнера

1
2
3
4
5

def horner(c, x):
    if len(c) == 1:
        return c[0]
    else:
        return c[0] + x * horner(c[1:], x)

Архив с файлом можно взять здесь.

Важно отметить, что уменьшение размера задачи, начиная с c_n вместо c₀, не приводит к схеме Горнера. В этом случае рекурсивная формула была бы такой:

    p(c, x) = p(c_0...n-1, x) + c_nxⁿ,

- и вычисляла бы полином, как в (4.5). Если бы степень xⁿ вычислялась за линейное или логарифмическое время, то метод потребовал бы Θ(n²) или Θ(n log n) операций соответственно. Однако схема Горнера более эффективна, так как полином вычисляется за линейное время (Θ(n)).

На следующем шаге мы рассмотрим треугольник Паскаля.

Предыдущий шаг Содержание Следующий шаг