Algorytmy - część druga kursu

Najważniejsze algorytmy

Kontynuujemy naszą przygodę z algorytmiką. Osoby, które jeszcze tego nie zrobiły, zapraszamy do przeczytania części pierwszej niniejszego kursu. A w tej części zapoznamy się z algorytmami...

• wyszukiwania wartości minimalnej w tablicy
• wyliczania wartości wielomianu za pomocą schematu Hornera
• potęgowania binarnego
• prostego sortowania tj.:
  • z sortowaniem bąbelkowym (z ang. Bubble Sort)
  • z sortowaniem metodą prostego wyboru (z ang. Selection Sort – SELSORT)
  • z sortowaniem metodą prostego wstawiania (z ang. Insertion Sort – INSSORT)

I. Rozgrzewka

W trakcie pierwszej lekcji przygotowaliśmy pojęcia i metody niezbędne do dalszej pracy i jesteśmy już gotowi do „wbicia zębów” w poważniejsze algorytmy. Z większością podanych tutaj problemów każdy programista spotyka się już na początku swojej (jak by nie było) twórczej działalności.

Na początek przyglądnijmy się prostemu algorytmowi wyszukiwania minimum.

1. Algorytm wyszukiwania minimum

Mamy tablicę liczb i chcemy w niej znaleźć najmniejszą wartość nic nie wiedząc o rozkładzie danych. Nie jest to problem szczególnie trudny, a najlepszym jego rozwiązaniem jest tzw. algorytm naiwny: przeglądnij całą tablicę, zapamiętując wartość lub pozycję najmniejszego dotychczas odwiedzonego elementu.

Algorytm zapiszemy następująco (w wersji znajdującej najmniejszą wartość):

Założenia:  A[1..n] - tablica liczb  Algorytm:      min := A[1];     FOR i := 2 TO n DO         IF A[i] < min THEN min := A[i]     wypisz(min); 

Na samym początku pierwszym elementem z tablicy inicjujemy zmienną min. Wpisanie tam np. 0 byłoby całkowicie bezsensowne gdyby np. wszystkie liczby w tablicy były większe od 0. Podany algorytm niezwykle łatwo przerabia się na wersję wyszukującą indeks najmniejszego elementu, lecz pozostawiam to jako ćwiczenie dla Czytelnika.

Przeanalizujmy teraz złożoność algorytmu:

• złożoność pamięciowa jest stała - nie używamy żadnych znaczących zmiennych pomocniczych,
• złożoność obliczeniowa jest liniowa - O(n). Musimy przejść dokładnie jeden raz przez każdy element tablicy. Warto zaznaczyć, że jest to rozwiązanie optymalne, tzn.: dla tak postawionego problemu nie istnieje lepszy algorytm.

2. Wyliczanie wartości wielomianu za pomocą schematu Hornera

Wielomiany są jednymi z ważniejszych funkcji matematycznych, a wyliczanie ich wartości jest dla matematyka trywialnym zadaniem. Gdy nie zależy nam zbytnio na szybkości programu, możemy spokojnie zastosować algorytm naiwny tj.:

Założenia:  W algorytmie zastosujemy konstrukcję DOWNTO:  FOR [zmienna] := [początek] DOWNTO [koniec] DO [instrukcje]  Jest to pętla odliczająca od wartości [początek] "w dół" do wartości [koniec].  FOR i := n DOWNTO k DO     wypisz(i)  Odpowiednik w Pascalu:  FOR i := n DOWNTO k DO writeln(i);  W C++:  for (i = n; i >= k; i--) cout << i; 

Zalozmy ze funkcja pow(x,y) oblicza wartość x podniesioną do potęgi y (x to wartość do obliczenia, a A[0..n] to współczynniki wielomianu):

Algorytm:  wynik := 0; FOR i := n DOWNTO 0 DO     wynik := wynik + A[i]*pow(x,i) 

Algorytm sprawia wrażenie optymalnego, jednak zastosowana w nim funkcja pow, którą najpewniej załadujemy ze standardowej biblioteki języka (np. cmath), jest w tym przypadku daleka od optimum. Możemy przyjąć, że w większości wypadków funkcja ta będzie realizowana następująco:

pow(x,i):     wynik := 1;     FOR k := 1 TO i DO         wynik := wynik * x      RETURN wynik; 

Wykonuje ona dokładnie i mnożeń. Jeśli zastosujemy ją do obliczania wielomianu, to np. dla wielomianu piątego stopnia wykonamy w samej funkcji pow 15 mnożeń.

Początkującym programistom może wydawać się, że koszt operacji mnożenia można zaniedbać, jednak działanie to nie jest dla procesora czymś prostym. Najczęściej stosuje on algorytmy podobne do szkolnych metod dodawania i mnożenia "w słupku". O ile dodawanie binarne jest proste i zajmuje procesorowi jeden cykl (pomijając pewne szczegóły techniczne związane z dostępem do pamięci), to mnożenie wymaga już kilku dodawań, a zatem zajmuje kilka cykli rozkazowych (choć nowe układy mają pewne usprawnienia w tej dziedzinie).

Rozwiązaniem jest schemat Hornera, który polega na wykorzystaniu dość istotnej własności wielomianów. Wyłączając kolejne potęgi liczby x przed nawias, otrzymujemy następującą formułę:

Co łatwo zapisać w postaci algorytmu:

Założenia:  A[0..n] - współczynniki wielomianu x – argument, dla którego chcemy obliczyć wartość wielomianu  Algorytm:      wynik := A[n]     FOR i := n-1 DOWNTO 0 DO         wynik := wynik*x + A[i] 

Ten prosty fragment kodu za jednym zamachem załatwia obliczanie potęg i końcowej wartości wielomianu. Najważniejszą jego cechą jest jednak to, że wykonuje jedynie n mnożeń (gdzie n to stopień wielomianu).

Złożoności:

• pamięciowa: O(1) - żadnych dodatkowych zmiennych,
• obliczeniowa: O(n) - dodatkowo, jest to optymalny algorytm obliczania wartości wielomianów.

3. Potęgowanie binarne

Skoro już wspomnieliśmy o potęgowaniu, to omówię teraz szybki algorytm dla tego działania. Opiera się on na systemie binarnym, wykorzystywanym w komputerach, oraz na obliczonych wcześniej pośrednich wartościach potęgi. Dokładniejszą jego analizę pozostawiam Czytelnikowi jako ćwiczenie.

Algorytm:  power(x,n):     wynik := 1;     WHILE n <> 0 DO         IF n MOD 2 <> 0 DO             wynik := wynik * x             n := n - 1         ELSE             x := x * x             n := n / 2      RETURN wynik  Przykładowa implementacja w C++:  int power(int x, int n) {     int wynik = 1;     while (n != 0)     {         if (n % 2 != 0)         {             wynik *= x;             --n;         }         else             {                 x *= x;                 n = n >> 1; // bitowe przesunięcie w prawo - równoważne podzieleniu przez 2             }     }     return wynik; } 

Złożoność:

• pamięciowa: O(1),
• obliczeniowa: O(log₂n) – zostanie wykonany ZDECYDOWANIE SZYBCIEJ niż w wypadku metody naiwnej.