Login lub e-mail Hasło   

Schemat Hornera

Wprowadzenie Schemat Hornera nie jest typowym, normalnym algorytmem. Jest to jedynie efektywniejszy sposób liczenia wartości wielomianów. Ponieważ mnożenie zajmuje...
Wyświetlenia: 9.506 Zamieszczono 29/10/2006

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.

Podobne artykuły


8
komentarze: 79 | wyświetlenia: 1153
111
komentarze: 32 | wyświetlenia: 60727
54
komentarze: 56 | wyświetlenia: 32590
54
komentarze: 68 | wyświetlenia: 31293
50
komentarze: 27 | wyświetlenia: 63526
49
komentarze: 18 | wyświetlenia: 64978
39
komentarze: 50 | wyświetlenia: 23278
39
komentarze: 30 | wyświetlenia: 28846
37
komentarze: 9 | wyświetlenia: 28520
36
komentarze: 37 | wyświetlenia: 23498
34
komentarze: 21 | wyświetlenia: 26317
32
komentarze: 12 | wyświetlenia: 26675
 
Autor
Artykuł




Brak wiadomości


Dodaj swoją opinię
W trosce o jakość komentarzy wymagamy od użytkowników, aby zalogowali się przed dodaniem komentarza. Jeżeli nie posiadasz jeszcze swojego konta, zarejestruj się. To tylko chwila, a uzyskasz dostęp do dodatkowych możliwości!
 

© 2005-2018 grupa EIOBA. Wrocław, Polska