Strona główna » Algorytmy » Artykuły » Algorytm Hornera
 

Algorytm Hornera

Wstęp

Opisane dalej funkcje działają w oparciu biblioteke wielomiany.h, której funkcje są opisane w poprzednich częściach tej serii.

Implementacja

Wyznaczanie wartości wielomianu

Najprostszym sposobem wyliczania wartości wielomianu jest branie każdego współczynnika po kolei (od a0 do an), gdzie dla ai wyliczymy wartość xi. Sumując wszystkie takie wyniki otrzymujemy wartość wielomianu dla podanego argumentu x. Sposób takiego wyliczania przedstawia poniższy kod:

  1. double wartosc_wielomianu(wielomian* w, double x){
  2.   double wynik = 0;
  3.   for(int i = 0; i <= w->stopien; i++)
  4.     wynik += zwrocWyrazStn(w, i)*pow(x, i);
  5.   return wynik;
  6. }

(1.) Jako argumenty przyjmuje wskaźnik na wielomian w oraz argument x. Wynikiem będzie liczba rzeczywista (double). (2.) Wszystkie kolejne wyliczenia zsumujemy do zmiennej wynik. (3.) Dla każdego współczynnika: (4.) pobieramy jego wartość i mnożymy przez xi. Na koniec (5.) zwracamy wynik.

Przeanalizujmy teraz ilość operacji arytmetycznych do wykonania. Dla wielomianu stopnia n mamy n operacji dodawania oraz mnożenia. Co w sumie daje złożoność Θ(n2). W przypadku wykorzystania pamięci mamy tylko jedną zmienną.

Poprawa wydajności

Zwiększmy teraz szybkość kosztem wykorzystania pamięci - dodamy dodatkową zmienną pot, która zaoszczędzi nam wyliczania wartości potęgi x przy każdym współczynniku.

  1. double wartosc_wielomianu2(wielomian* w, double x){
  2.   double wynik = 0;
  3.   double pot = 1;
  4.   for(int i = 0; i <= w->stopien; i++){
  5.     wynik += zwrocWyrazStn(w, i)*pot;
  6.     pot *= x;
  7.   }
  8.   return wynik;
  9. }

Deklarujemy dwie zmienne: (2.) wynik do przechowywania wyniku oraz (3.) pot. (4.) Dla każdego współczynnika: (5.) dodajemy wartość i-tego współczynnika pomnożoną przez wartość pot. (6.) Mnożymy pot razy x. Na koniec (7.) zwracamy wynik.

Ponownie wykonujemy n operacji dodawania, ale zmniejszyliśmy liczbę operacji mnożenia. W każdej iteracji mnożymy dokładnie dwa razy, dlatego złożoność obliczeniowa dla tego algorytmu jest Θ(n), ale wzrosło nam wykorzystanie pamięci - korzystamy teraz z dwóch zmiennych. Oczywiście dla użytkownika nie ma to znaczenia. Jednak w przypadku bardziej złożonych algorytmów i systemów każdy zaoszczędzony bit to sukces.

Algorytm Hornera

Przypomnijmy sobie definicje wielomianu:

w(x) = anxn + an - 1xn - 1 + ... + a1x + a0

przekształćmy go do postaci:

w(x) = ((.. ((a0x+a1)x + a2 + .. an - 2)x + an - 1)x + an

Zgodnie z wzorem obliczmy wartość wielomianu przyjmują początkowo w jako a0:

  1. double horner(wielomian* w, double x){
  2.   double wynik = zwrocWyrazStn(w, w->stopien);
  3.   for(int i = w->stopien - 1; i >= 0; i--)
  4.     wynik = wynik * x + zwrocWyrazStn(w, i);
  5.   return wynik;
  6. }

(2.) Wynik ustalamy jako współczynnik przy najwyższej potędze x. (3.) Dla każdego pozostałego współczynnika mnożymy aktualny wynik razy x i dodajemy kolejny współczynnik. Na koniec (5.) zwracamy wynik.

W celu przekonania się, że jest to najbardziej optymalny algorytm spójrzmy na jego złożność. Wykonujemy n operacji dodawania i mnożenia co daje lepszą złożoność od pierwszej metody i taką samą jak w drugiej czyli Θ(n). Jednak deklarujemy znowu tylko jedną zmienną, więc jest to najbardziej optymalne rozwiązanie.

Testowanie funkcji

Poniższa funkcja main() pozwala przetestować działanie napisanych funkcji. Program na początku wczyta od użytkownika wielomian, wypisze go, a następnie zapyta dla jakiego argumentu ma zostać wypisana wartość wielomianu. Program wypisze na ekran wyliczoną wartość dla każdej napisanej metody.

  1. int main () {
  2.   wielomian* w = wczytajWielomian();
  3.   wypiszWielomian(w);
  4.   double x;
  5.   cout << "x? ";
  6.   cin >> x;
  7.   cout << "metoda 1:" << wartosc_wielomianu(w, x) << endl;
  8.   cout << "metoda 2:" << wartosc_wielomianu2(w, x) << endl;
  9.   cout << " horner:" << horner(w, x) << endl;
  10.   system("pause");
  11.   return 0;
  12. }