[WikiDyd] [TitleIndex] [WordIndex

To jeszcze nie jest gotowe

Algorytmy i struktury danych

Złożoność obliczeniowa 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:

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łóżmy, ż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

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

Uwaga 2: K(n)= c3 * n2 + c1 * n + 1000000000 jest O(n3) 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:

Notacja O

Koszt

O(1)

stały

O(n)

liniowy

O(n*log2(x)

quasi-liniowy

O(n^2)

kwadratowy

O(n^3)

sześcienny

O(2^n)

wykładniczy

O(e^n)

wykładniczy

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(n3)

np. 10*n3: 10^7 s

czyli ok. 115 dni

O(n2)

np. 10*n2: 103 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:

   1 void bubble( double v[], int n ) {
   2   int i;
   3   int changed;
   4 
   5   do {
   6     changed= 0;
   7     for( i=1; i < n; i++ )
   8       if( v[i-1] < v[i] ) {
   9         double tmp= v[i];
  10         v[i]= v[i-1];
  11         v[i-1]= tmp;
  12         changed= 1;
  13       }
  14   } while( changed );
  15 }

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:

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)) ?


2015-09-23 06:32