Wprowadzenie
Schemat Hornera nie jest typowym, normalnym algorytmem. Jest to jedynie efektywniejszy sposób liczenia wartości wielomianów. Ponieważ mnożenie zajmuje procesorowi bardzo dużo czasu, więc wszelkie ograniczenie tego działania w jakimkolwiek algorytmie zwiększa jego szybkość w znacznym stopniu. Na tym właśnie polega Schemat Hornera.
Przykład
Weźmy na przykład pod uwagę następujący wielomian:
7x4 + 3x3 + 5x2 + 9x + 1
Weźmy pod uwagę pierwsze cztery elementy naszego wielomianu. Możemy dla tych elementów wyłączyć wspólny czynnik przed nawias. Tym czynnikiem jest x:
(7x3 + 3x2 + 5x + 9)x + 1
Teraz "wyciągamy" przed nawias x z pierwszych trzech elementów w nawiasie:
((7x2 + 3x + 5)x + 9)x + 1
Następnie wyłączmy przed nawias następne x z dwóch pierwszych elementów w wewnętrznym nawiasie:
((7x + 3)x + 5)x + 9)x + 1
I to wszystko! Na tym polega cały schemat Hornera. Niby nic... Proszę teraz porównać liczbę mnożeń w początkowym wielomianie i w tym na końcu. Dla przejrzystości rozpiszę je:
7*x*x*x*x + 3*x*x*x + 5*x*x + 9*x + 1, czyli 10 mnożeń i 4 dodawania
((7*x + 3)*x + 5)*x + 9)*x + 1, czyli 4 mnożenia i 4 dodawania
Obydwa wyrażenia reprezentują to samo, ale dzięki zastosowaniu schematu Hornera drugie zawiera dużo mniej mnożeń.
Dla wielomianu n-tego stopnia w zwykłej postaci należy wykonać n*(1+n)/2 mnożeń, a dla wielomianu po zastosowaniu schematu Hornera tylko n mnożeń! Różnica jest olbrzymia.