Algorytmy i struktury danych
Informatyka, sem IV

Wykład 2: Analiza algorytmów I

Złożoność algorytmów
====================

Wyobraźmy sobie program obsługujący dużą hurtownię.
Jego działanie polega na przeczytaniu z dysku bazy danych
opisującej stan hurtowni i wykonanie ciągu n transakcji.
Załóżmy, że czytanie bazy z dysku zawsze trwa jedną minutę,
a wykonanie jednej transakcji 10 milisekund.
Czas działania programu w sekundach można wyrazić jako:

t = 60 + 10e-3 * n

Zauważmy, że pomimo iż 60 >> 10e-3, to dla dużych wartości n
czas działania programu będzie zależał głównie od liczby transakcji.
Jeżeli kupimy szybszy komputer, to oczywiście zmienią się
stałe (60 i 10e-3). Tak samo będzie jeżeli zmienimy kompilator,
czy zapiszemy algorytm w innym języku programowania.
W opisie szybkości algorytmów poszukujemy więc notacji,
która pominie stałe współczynniki (które wciąż maleją z rozwojem
technologii).

Do opisu złożoności obliczeniowej algorytmów używana jest najczęściej
notacja "wielkiego O", która krótko mówiąc, opisuje, jak zmienia się
czas działania algorytmu w proporcji do wielkości danych, które algorytm
przetwarza.

Formalnie:

Załózmy, że czas działania algorytmu (dla tak zwanego "najgorszego
przypadku") można opisać funkcją K(n),
gdzie n jest wielkościa danych (w bitach, słowach, czy liczbie
elementów tabkicy, czy jeszcze czymś innym).

Mówimy, że K(n) jest O( f(n) ) wtedy i tylko wtedy gdy istnieje taka stała
C, że K(n) <= C * f(n) dla każdego n >= N.

Przykład: koszt algorytmu obsługującego hurtownię to O(n).

t ^
| 0.02n K(n)
| / **
| / **
| | / **
180| | / **
| | / **
| |/**
120| |*
| */|
| **/ |
60** / |
| / |
|/ |
/-----+---------------------------> n
6000

Mamy C = 2e-2 i N = 6000

Formalnie:

O(f(n)) to zbiór wszystkich funkcji K(n), dla których
istnieją pary C, N, takie, że dla prawie wszystkich n >= N
K(n) <= C * f(n)

Uwaga 1:
nietrudno pokazać, że nasza funkcja K(n) jest też O(n^3)
Oszacowanie O jest więc tylko oszacowaniem
górnym i trzeba je wykonywać starannie, aby nie przeszacować.

Uwaga 2:
K(n)= c3 * n^2 + c1 * n + 1000000000 jest O(n^3)
Oszacowanie O bierze pod uwagę tylko dominujące składniki
w funkcji kosztu.

Uwaga 3:
10000000*n i 0.0000001*n są O(n)
Oszacowanie O nie troszczy się o stałe: dwa algorytmy tego
samego rzędu mogą zdecydowanie różnić sie szybkością.

Uwaga 4:
porównajmy algorytmy A1, K1= 100*n i A2, K2= n*log_2(n)
Pierwszy ma złożoność liniową, a drugi logarytmiczną
i jest, wydawałoby się, gorszy, ale tak naprawdę liczba
N, dla której K1(N) < K2(N) przekracza 1e30 (jest to
więcej niż oszacowanie liczby cząstek we Wszechświecie).

Ważniejsze typy złożoności:

O(1) - koszt stały
O(n) - koszt liniowy
O(n*log2(x) - koszt quasi-liniowy
O(n^2) - koszt kwadratowy
O(n^3) - -"- sześcienny
O(2^n) - koszt wykładniczy
O(e^n) - -"- -"-

Algorytmy o koszcie do O(n*log2(n)) uznawane są za
efektywne, a alogorytmy o koszcie O(n^4) i wyższym
za bezużyteczne.

Dlaczego ?

Wyobraźmy sobie zadanie o wielkości n=10^4
i komputer wykonujący milion (10^6) operacji na
sekundę. W zależności od rodzaju algorytmu
nasze zadanie będzie się liczyć:

O(n^3), np. 10*n^3: 10^7 s czyli ok. 115 dni
O(n^2), np. 10*n^2: 10^3 s czyli ok. 16 min, 40 s
O(n*log2(n)), np. 10*n*log2(n): nieco ponad 13 s
O(n), np. 10*n: 0.1 s

Patrząc od drugiej strony: mając do dyspozycji taki sam
komputer i różne algorytmy wykonania takiego zadania,
największe dane, dla których da się zakończyć obliczenia
w ciągu 24 godzin mają rozmiar (przyjmuję C=1):
Koszt | Maks. n
-------------+---------
O(n!) | 13 (prawie 14 ;-)
O(2^n) | 36
O(n^4) | 542
O(n^3) | 4420
O(n^2) | 293938
O(n*log2(n)) | ponad 2750 milionów
O(n) | ponad 86 miliardów

Oszacowanie O mówi, że algorytm nie będzie nigdy zachowywał się
"gorzej" niż określa to funkcja występująca po O.
Przydatne byłoby też jednak oszacowanie z drugiej strony -- w tym
celu stosuje się notację "Omega":

Omega(f(n)) to zbiór wszystkich funkcji takich, że istnieją
stałe dodatnie D i N takie, że dla prawie wszystkich
n >= N

K(n) >= D * f(n)

Omega jest odwrotnością "wielkiego O":
jeżeli K(n) jest O(f(n)) to f(n) jest Omega(K(n)).

Omega daje dolny kres oszacowania: mówi, że nie powinniśmy
oczekiwac, że nasz algorytm bedzie się zachowywał "lepiej".

Jeżeli mamy dla danego algorytmu zarówno oszacowanie
O(f(n)) jak i Omega(f(n)), to mówimy, że algorytm
należy do Teta(f(n))
(Teta to litera grecka, podobna do O przekreślonego poziomą kreską).

Przykład:



t ^
| 2n K(n)
| / *
| / ***
| | / *
| | / *
| | / | * .5n
| |/** | * ~~~
| |* * |* ~~~
| */| * ~|~
| **/ | ~* *|
** / | ~~~ * |
| / ~~~ |
|/~~~ | |
~-----+---------+-----------------> n
N1 N2

C = 2, D= 0.5

Notacja Teta jest symetryczna: jeżeli g(n) jest Teta(f(n))
to i f(n) jest Teta(g(n)).

Uwaga: zarówno Teta,jak i O dotyczą najgorszego przypadku.
Algorytm klasy Teta(n) dla pewnych danych może działać szybciej,
niż wynikałoby to z oszacowania.

Przykład -- sortowanie bąbelkowe:

dany jest wektor double v[n], sortujemy go rosnąco:

void bubble( double v[], int n ) {
int i;
int changed;

do {
changed= 0;
for( i=1; i < n; i++ )
if( v[i-1] < v[i] ) {
double tmp= v[i];
v[i]= v[i-1];
v[i-1]= tmp;
changed= 1;
}
} while( changed );
}

Algorytm jest dla najgorszego przypadku O(n^2) (dowód?),
ale dla danych już posortowanych (albo pewnych prawie posortowanych)
może działać w czasie liniowym (proszę podać przykład takich danych).

Pełny koszt algorytmu
=====================

W celu pełnego oszacowania czasu działania algorytmu szacuje się
liczbę wszystkich jednostkowych operacji wykonywanych w trakcie działania
algorytmu:
- wykonanie operatora arytmetycznego, relacyjnego lub logicznego;
- nadanie wartości zmiennej prostej;
- obliczenie wartości zmiennej indeksowanej (elementu tablicy),
wskazywanej lub składnika struktury;
- wywołanie procedury lub funkcji;
- przekazanie wartości parametru z i do procedury;
- wykonanie instrukcji sterującej.

Analizując złożoność obliczeniową algorytmów ograniczamy się do takich algorytmów,
które dają się rozłożyć na tak zdefiniowane operacje.

Przykład:

1: int pierwsza( int n ) {
2: int i= 2;
3: for( ; i*i < n; i++ )
4: if( n % i == 0 )
5: return 0; /* n dzieli sie przez i - nie jest pierwsza */
6: return 1; /* sprawdzilismy wszystkie liczby <2,sqrt(n)> - n jest l. pierwsza */
7: }

W wierszu 2 wykonujemy jedną operację, w wierszu 3 - 3 operacje, w wierszu 4 dwie
i w wierszu 5 i 6 po jednej.

Jeżeli n jest 1..4 to wykonamy wiersze 2,3,6 czyli 4 operacje (bez i++ w 3),
jeżeli n jest parzyste > 4: 2,3,4,5 czyli 6 operacji
dla n będącego liczbą pierwszą mamy 2+sqrt(n)-1 operacji
dla n będącego kwadratem liczby pierwszej mamy 2+sqrt(n) operacji

Czy algorytm jest Teta(sqrt(n)) ?