CALCOLO  DEL VALORE DI UN POLINOMIO

Un esempio interessante, e semplice, di riduzione della complessità, è quello del metodo di Horner per il calcolo del valore del polinomio in una variabile, che fa diminuire il numero delle operazioni da effettuare e riduce così la complessità da n² a  n.

METODO ORDINARIO

 b        ax + b               ax² + bx + c                 ax³ + bx² + cx + d                ax⁴ + bx³ + cx² + dx + e

 0       (1 + 1)               2 + (1 + 2)                     2 + 3 +  (1 + 3)                     2 + 3 +  4 + (1 + 4)

Si vede che all’aumentare del grado del polinomio di una unità il numero delle operazioni aumenta di un numero pari a (1 +  grado del polinomio)

Infatti si aggiunge sempre una addizione e una moltiplicazione e una potenza che dà un numero di operazioni pari al grado del polinomio meno uno. 

Quindi  se N è il numero delle operazioni si ottiene

N = 2 + 3 + 4 + ...+ n + 1 = 1 + (1 +  2  + 3 + 4 + ... + n) + (1+1+1+1+1+ ... ) = 1 + n*(n+1)/2 + n-1

     n-1 volte

N = (n² + 3n)/2                        n = grado del polinomio 

complessità O(n²)

METODO DI HORNER

ax + b              (ax + b)x + c               ((ax + b)x + c)x + d                 (((ax + b)x + c)x + d)x + e

    2                       2 + 2                              2 + 2 + 2                                 2 + 2 + 2 + 2

All’aumentare del grado si ha sempre un aumento di due operazioni.

Si capisce inoltre che si risparmiano operazioni perché se devo fare 

5*3 + 5*7 + 5*9  

e faccio invece  

5*(3 + 7 + 9) 

si vede con chiarezza che la moltiplicazione per 5 invece di farla 3 volte la faccio solo due volte.

Se quindi N è il numero delle operazioni

N = 2n                n = grado del polinomio                  (complessità O(n))