PODSTAWY INFORMATYKI - ZŁOŻONOŚĆ, EFEKTYWNOŚĆ, ZASADY ANALIZY ALGORYTMÓW



Analiza algorytmów

Analiza algorytmów – dział informatyki zajmujący się szukaniem najlepszych algorytmów dla zadań komputerowych. Udziela odpowiedzi na pytania:

Analiza algorytmów prowadzona jest w dwóch podstawowych aspektach:

Celem analizy algorytmów jest budowanie optymalnych, efektywnych i poprawnych semantycznie algorytmów.

Złożoność obliczeniowa algorytmu

Złożoność obliczeniowa algorytmu – ilość zasobów komputerowych potrzebnych do jego wykonania:

Można wyróżnić:

Dokładniejszy opis zagadnień dotyczących złożoności obliczeniowej oraz sposoby analizy algorytmów można znaleźć np. tutaj!

Zasadniczo rozróżniamy następujące złożoności obliczeniowe:

Jeśliby założono, że pojedyncza instrukcja wykonuje się jedną nanosekundę (czyli na komputerze działającym z częstotliwością 1 GHz) wtedy czasy wykonania względem rozmiaru danych wyglądałyby następująco:

Złożoność obliczeniowa względem rozmiaru danych wejściowych
Rozmiar danych: 10 20 50 100 200 1000
log n 3,32 ns 4,23 ns 5,64 ns 6,64 ns 7,64 ns 9,97 ns
n 10 ns 20 ns 50 ns 100 ns 200 ns 1 μs
n log n 33,21 ns 86,44 ns 282,2 ns 664,4 ns 1,53 μs 9,97 μs
n2 100 ns 400 ns 2,5 μs 10 μs 40 μs 1 ms
2n 1 μs 1,05 ms 13 dni 4·1013 lat 5,1·1043 lat 3,4·10284 lat
n! 3,6 ms 77 lat 9,6·1044 lat 3·10141 lat 2,5·10358 lat 1,27·102551 lat

Jeśli więc jesteśmy w stanie rozwiązać postawione zadanie algorytmem o złożoności nie większej niż wielomianowej, wtedy mamy szansę na rozwiązanie zadania w realnym/rozsądnym czasie. Jeśli zaś algorytm posiada złożoność ponadwielomianową, wtedy w praktyce wykonywanie algorytmu dla większej ilości danych, nigdy się ne zakończy,gdyż często rozwiązanie trwałoby dłużej niż szacowany wiek Wszechświata (ok. 1010 lat)! Warto więc rozważać złożoność obliczeniową algorytmów, gdyż bez niej nawet dokładny i poprawny algorytm może się dla nas realnie nigdy nie zakończyć!

W praktyce dzielimy algorytmy wg ich złożoności na 2 klasy:

Jeśli jedna część algorytmu o złożoności Θ(log n) zawiera się w pętli wykonywanej n razy, wtedy złożoność całego kodu będzie:
Θ(n)⋅Θ(log n) = Θ(n log n)

Algorytm ma taką złożoność, jak jego najbardziej czasochłonny fragment, np.:
Θ(n) +Θ(n2 ) = Θ(n + n2 ) = Θ(n2 )

Złożoność czasowa

Złożoność czasowa powinna być własnością samego algorytmu jako metody rozwiązania problemu, więc powinna być niezależna od komputera, języka programowania czy sposobu jego kodowania. W tym celu wyróżnia się tzw. operacje dominujące – takie, których łączna liczba jest proporcjonalna do liczby wykonań wszystkich operacji jednostkowych w dowolnej komputerowej realizacji algorytmu. Za jednostkę czasową przyjmuje się wykonanie jednej operacji dominującej.

[Rozmiar: 153436 bajtów]

Złożoność pamięciowa

To ilość dodatkowych jednostek pamięci (najczęściej bajtów lub bitów) potrzebnych do rozwiązania problemu danym algorytmem. Złożoność pamięciową wyrażamy również jako funkcję rozmiaru danych.

Sortowanie szybkie - Quicksort

Sortowanie szybkie wykorzystuje metodę dziel i zwyciężaj. Może być zaimplementowane przy pomocy rekurencji oraz iteracyjnie.

program SortowanieSzybkie

procedure sortuj(p,k: indeks); {p - początek sortowanego przedziału, k - koniec sortowanego przedziału}
var i,j: indeks; x,w: obiekt;
begin i:=p; j:=k;
x := a[(p+k) div 2];
repeat
while a[i].klucz < x.klucz do i:=i+1;
while a[j].klucz > x.klucz do j:=j-1;
if i<=j then begin w:=a[i]; a[i]:=a[j]; a[j]:=w; i:=i+1; j:=j-1; end
until i>j
if p<j then sortuj (p,j);
if i<k then sortuj (i,k)
end;

{Program główny:}
begin sortuj (1,n);
end.

Prześledźmy sortowanie szybkie na przykładzie:

[Rozmiar: 47219 bajtów]

Badanie efektywności algorytmów

Polega na oszacowaniu ich złożoności czasowej i pamięciowej. Poszczególne części algorytmu badane są pod kątem ilości operacji dominujących (porównań, operacji arytmetycznych, przestawień itp.) W zależności od zastosowania oraz rodzaju i rozmiaru przetwarzanych struktur danych można wyróżnić różne operacje dominujące. Podczas sortowania szybkiego po wybraniu ograniczenia x (zajmującego m-te miejsce tablicy) posuwamy się przez całą tablicę dokonując dokładnie n porównań. Liczbę wymian szacujemy probabilistycznie jako liczbę elementów lewego (mniejszego) podziału równą n-m razy prawdopodobieństwo zamiany klucza równe (n-m+1)/n. Sumując po wszystkich możliwych wyborach ograniczenia x i dzieląc przez ich liczbę n otrzymujemy:
[Rozmiar: 10721 bajtów]
Stąd spodziewana liczba wymian wynosi około n/6. Jeśli udałoby się zawsze jako ograniczenie wybrać medianę, to każdy proces podziału rozbije tablicę na dwie jednakowe części, a wówczas potrzebna do posortowania tablicy liczba przejść będzie równa log n. Więc całkowita liczba porównań wynosić będzie n log n, a całkowita liczba wymian n/6 · log n. Nie można jednak liczyć na to, że zawsze jako ograniczenie zostanie wybrana mediana, gdyż szansa trafienia na nią wynosi 1/n, jednak przy losowym wyborze ograniczenia średnia efektywność sortowania szybkiego jest gorsza od optymalnej tylko o 2 · ln 2 razy (im bliżej mediany trafimy tym lepiej – zadanie jest dobrze uwarunkowane). Jeżeli jako ograniczenie zostałby wybrany zawsze największy lub najmniejszy obiekt, wtedy potrzeba wykonać n podziałów, co powoduje spadek efektywności metody do poziomu n2.

Sortowanie szybkie charakteryzuje się oczekiwaną złożonością czasową Θ(n log n). Sortowanie szybkie jest sortowaniem niestabilnym!

[Rozmiar: 87630 bajtów]

Jaka jest złożoność wstawiania, usuwania, pobierania, sortowania, szukania elementu w liście podwójnie wiązanej?

[Rozmiar: 48897 bajtów]

Sortowanie przez zliczanie - Counting Sort

Załóżmy, że każdy z n sortowanych elementów jest liczbą całkowitą z przedziału od 1 do k dla pewnego ustalonego k takiego, że k = O(n). Wtedy sortowanie przez zliczanie działa w czasie O(n).
Idea: Dla każdej liczby wejściowej x wyznaczamy, ile elementów jest od niej mniejszych. W ten sposób znamy dokładną pozycję x w posortowanym ciągu, więc możemy ją bezpośrednio na tej pozycji umieścić.

procedure Counting-Sort;
var i : integer;
begin
for i := 1 to k do c[i] := 0; // O(k)
for i := 1 to n do c[a[i]] := c[a[i]] + 1; // c[i] zawiera liczbę elementów = i O(n)
for i := 2 to k do c[i] := c[i] + c[i-1]; // c[i] zawiera liczbę elementów ≤ i O(k)
for i := n downto 1 do // O(n)
begin
b[c[a[i]]] := a[i];
c[a[i]] := c[a[i]] - 1;
end
end {Counting-Sort}; // Przy założeniu, że k = O(n), O(n+k) = O(n)
[Rozmiar: 67809 bajtów]

Złożoność czasowa działania algorytmu przez zliczanie (który nie wykorzystuje porównań!) wynosi O(n), a więc mniej niż wynosi dolna granica sortowań za pomocą porównań. Algorytm ten jest stabilny, gdyż liczby o tych samych wartościach występują w tablicy wynikowej w takiej samej kolejności, jak w tablicy początkowej. Stabilność algorytmu sortowania jest tylko wtedy istotna, gdy z sortowanymi danymi są związane dodatkowe dane, które np. mogą być już posortowane wg innego klucza, zaś brak stabilności algorytmu spowodowałby zniszczenie uzyskanego wcześniej porządku.

Sortowanie pozycyjne - Radix Sort

W sortowaniu pozycyjnym stosujemy pewien trik, polegający na posortowaniu w pierwszej kolejności najmniej znaczących cyfr/znaków/itd. (niejako od końca). Następnie sortujemy według drugiej, trzeciej, ... najmniej znaczącej cyfry/znaku powtarzając cały proces dla wszystkich d pozycji cyfr/znaków. Do sortowania stosujemy algorytm sortowania przez zliczanie, gdyż jego stabilność zapewnia poprawność sortowania pozycyjnego, dodatkowo zapewniając jego szybkość.

procedure Radix-Sort;
var i : integer;
begin
for i := 1 to d do Counting-Sort (A wg. cyfry i);
end {Radix -Sort};
[Rozmiar: 31730 bajtów]

Jeżeli każda z cyfr należy do przedziału 1..k, a k nie jest zbyt duże, to należy użyć sortowania przez zliczanie. Wtedy każdy przebieg przez n d-cyfrowych liczb wymaga czasu Θ(n+k), co daje w sumie Θ(dn+dk), jeśli zaś d jest stałą i k=O(n), to sortowanie pozycyjne działa w czasie liniowym O(n).   Sortowanie pozycyjne odgrywa szczególną rolę wtedy, gdy do posortowania rekordów danych wykorzystuje się klucz składający się z wielu pól:

Sortowanie kubełkowe - Bucket Sort

Sortowanie kubełkowe stosujemy przy założeniu, że dane wejściowe będą liczbami rzeczywistymi wybieranymi z przedziału [0, 1) zgodnie z rozkładem jednostajnym (tj. taki, że dla każdego zdarzenia elementarnego s należącego do przestrzeni skończonej prawdopodobieństwo wynosi 1/|S|). Idea sortowania kubełkowego opiera się na triku polegającym na podziale przedziału [0,1) na n podprzedziałów jednakowych rozmiarów, tzw. kubełków, a następnie „rozrzuceniu” n liczb do kubełków, do których należą. Ponieważ liczby są jednostajnie rozłożone w przedziale [0,1), więc oczekujemy, że w każdym kubełku nie będzie ich zbyt wiele. Aby otrzymać ciąg wynikowy, sortujemy najpierw liczby w każdym z kubełków, a następnie wypisujemy je, przeglądając kolejno kubełki. Kubełki implementujemy w postaci list, do których wstawiamy elementy przy pomocy algorytmu sortowania przez proste wstawianie. W ten sposób uzyskujemy kubełki składające się z posortowanych elementów.

procedure Bucket-Sort;
var i : integer;
begin
for i := 1 to n do Wstaw a[i] do posortowanej listy b[ n * a[i] ];
Połącz listy b[0], b[1], ..., b[n-1];
end {Bucket -Sort};
[Rozmiar: 67389 bajtów]

Pesymistyczny czas wstawiania kolejnych elementów do n list algorytmem prostego wstawiania wynosi, gdyż ze względu na przyjętą jednostajność rozkładu.

Mediana

Mediana (median) – to taki element zbioru, od którego w tym zbiorze jest tyle samo elementów większych lub równych co mniejszych lub równych. Jeśli zbiór Z jest posortowany rosnąco, to:

Istnieją również pojęcia dolnej mediany (lower median) i górnej mediany (upper median), które w tym przypadku oznaczają odpowiednio element Z[n/2-1] i Z[n/2] w ciągu uporządkowanym o parzystej liczbie elementów.
Mediana posiada wiele ważnych zastosowań praktycznych w statystyce, grafice, obróbce dźwięku i wielu innych dziedzinach.

Liczby pierwsze

Liczby pierwsze pełnią niezwykle ważne zadanie w matematyce oraz wszelkiego rodzaju algorytmach szyfrowania danych ze względu na to, iż nie są podzielne przez inne liczby tylko przez siebie same i przez 1.

Liczby pierwsze możemy najprościej wyznaczyć przez sprawdzenie ich podzielności przez inne liczby mniejsze od nich. Czy można efektywniej?

[Rozmiar: 36383 bajtów]

Sito Eratostenesa – jeśli ze zbioru usuniemy wszystkie wielokrotności liczby pierwszej 2, potem 3, potem kolejnej jaka pozostała, czyli 5, bo 4 już zostało zredukowane, to w wyniku otrzymamy listę/tablicę liczb pierwszych. Nazwa „sito” pochodzi od czynności odsiewania kolejnych wielokrotności liczb pierwszych ze zbioru liczb.

[Rozmiar: 51575 bajtów]

Sito Atkina-Bernsteina rozpoczyna pracę ze zbiorem S, w którym wszystkie liczby są zaznaczone jako złożone (czyli nie pierwsze). Algorytm zupełnie ignoruje liczby podzielne przez 2, 3 lub 5 i opiera swoje działanie na następujących faktach matematycznych:

  1. Wszystkie liczby dające resztę z dzielenia przez 60 równą 0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40, 42, 44, 46, 48, 50, 52, 54, 56 lub 58 są podzielne przez 2, zatem nie są pierwsze - algorytm je ignoruje.
  2. Wszystkie liczby dające resztę z dzielenia przez 60 równą 3, 9, 15, 21, 27, 33, 39, 45, 51 lub 57 są z kolei podzielne przez 3 i również nie są pierwsze - algorytm je ignoruje.
  3. Wszystkie liczby dające resztę z dzielenia przez 60 równą 5, 25, 35 lub 55 są podzielne przez 5 i nie są pierwsze - algorytm je ignoruje.
  4. Wszystkie liczby dające resztę z dzielenia przez 60 równą 1, 13, 17, 29, 37, 41, 49 lub 53 posiadają resztę z dzielenia przez 12 równą 1 lub 5. Liczby te są pierwsze wtedy i tylko wtedy, gdy liczba rozwiązań równania 4x2 + y2 = n jest nieparzysta dla x,y ∈ N, a liczba n nie jest kwadratem innej liczby naturalnej.
  5. Wszystkie liczby dające resztę z dzielenia przez 60 równą 7, 19, 31 lub 43 posiadają resztę z dzielenia przez 12 równą 7. Są one liczbami pierwszymi wtedy i tylko wtedy, gdy liczba rozwiązań równania 3x2 + y2 = n jest nieparzysta dla x,y ∈ N, a liczba n nie jest kwadratem innej liczby naturalnej.
  6. Wszystkie liczby dające resztę z dzielenia przez 60 równą 11, 23, 47 lub 59 posiadają resztę z dzielenia przez 12 równą 11.  Są one liczbami pierwszymi wtedy i tylko wtedy, gdy liczba rozwiązań równania 3x2 − y2 = n jest nieparzysta dla x,y ∈ N, a liczba n nie jest kwadratem innej liczby naturalnej.

[Rozmiar: 109533 bajtów]

Przekazywanie danych do procedury lub funkcji przez wartość lub referencję

Na efektywność działania programu wpływa również wielkość struktur danych, jakie są przekazywane do procedur lub funkcji, oraz częstość ich wywoływania. Dlatego warto rozważyć, w jaki sposób dane te będą przekazywane. Ponadto ma to również istotny wpływ na możliwość zwracania wyników działania funkcji i procedur do programu głównego lub funkcji/procedury nadrzędnej. Jeśli dane są przekazywane przez referencję, wyniki zapisane wewnątrz funkcji są automatycznie zwracane bez dodatkowych operacji, jakie należałoby poświęcić na zwrócenie tych wartości w odwrotnym wypadku.

Istnieją dwa sposoby przekazywania danych do funkcji lub procedury:

[Rozmiar: 21613 bajtów]