Złożoność obliczeniowa i pamięciowa algorytmów

Program komputerowy rozwiązujący określony problem posiada do swej dyspozycji dwa podstawowe zasoby:

Przez czasową złożoność obliczeniową (ang. time computational complexity lub time complexity) rozumiemy ilość czasu niezbędnego do rozwiązania problemu w zależności od liczby danych wejściowych. Złożoność czasowa jest zatem pewną funkcją liczby danych wejściowych:

 

T(n) = f(n)

 

Na przykład:

 

T(n) = 2n2 - 3n + 15

 

Złożoność czasową wyrażamy albo w jednostkach czasu, albo w liczbie operacji dominujących, które należy wykonać dla n danych, aby otrzymać rozwiązanie problemu. Operacja dominująca jest operacją, której wykonanie bezpośrednio wpływa na czas wykonania całego algorytmu. Podawanie złożoności czasowej w jednostkach czasu jest niewygodne, ponieważ wynik zależy od szybkości komputera, na którym dokonano pomiarów - trudno takie wyniki odnieść do innych komputerów, szczególnie wyposażonych w inne procesory, gdzie czas wykonania podobnych operacji może znacznie się różnić. Dlatego częściej złożoność czasową wyrażamy w liczbie operacji dominujących, gdyż każdy komputer, bez względu na swoje własności, operacje te musi wykonać. Dzięki temu wynik uniezależniamy od faktycznej szybkości komputerów

Złożoność pamięciowa (ang. space computational complexity lub space complexity) określa z kolei liczbę komórek pamięci, która będzie zajęta przez dane i wyniki pośrednie tworzone w trakcie pracy algorytmu.

 

Ponieważ często zużycie zasobów w algorytmie uzależnione jest od postaci przetwarzanych danych, zarówno złożoność czasowa jak i pamięciowa może występować w trzech odmianach:

Aby poglądowo wyjaśnić powyższe terminy, rozważmy prosty algorytm wyszukiwania robaczywego jabłka w koszu n jabłek. Algorytm jest bardzo prosty:

 

Dopóki w koszu są jabłka, wybierz jabłko z kosza, obejrzyj je, jeśli jest robaczywe, to zakończ. Inaczej odłóż je na bok i kontynuuj z następnym jabłkiem.

 

Rozważmy, ile operacji dominujących (ocena jabłka) wykona ten algorytm dla n jabłek.

  1. Zakładamy przypadek optymistyczny - robaczywe jabłko napotkamy za pierwszym razem. Zatem:
    To(n) = 1 - złożoność optymistyczna
  2. Zakładamy przypadek najgorszy - w koszu brak jabłek robaczywych lub robaczywe jabłko będzie wyjęte z kosza jako ostatnie:
    Tw(n) = n - złożoność pesymistyczna
  3. W przypadku typowym robaczywe jabłko znajdziemy po przeglądnięciu połowy jabłek w koszu - tzn. raz będzie ono wyciągnięte wcześniej, raz później, a średnio w n/2 teście:
    TA(n) = n/2 - złożoność średnia, oczekiwana

Zatem podsumowując:

Złożoność optymistyczna określa zużycie zasobów dla najkorzystniejszego zestawu danych.

Złożoność średnia określa zużycie zasobów dla typowych (tzw. losowych) danych.

Złożoność pesymistyczna określa zużycie zasobów dla najbardziej niekorzystnego zestawu danych.

 

Określanie czasowej złożoności obliczeniowej algorytmu

Dla przykładu obliczymy złożoność czasową algorytmu obliczania sumy kolejnych liczb naturalnych. Dla każdej operacji określimy symboliczne czasy wykonania, które oznaczymy małymi literkami t z odpowiednim indeksem. Następnie czasy te zsumujemy i otrzymamy w ten sposób wzór na czasową złożoność obliczeniową tego algorytmu.

 

Wejście:

n - określa ile kolejnych liczb naturalnych ma być sumowane

 

Wyjście:

suma n kolejnych liczb naturalnych

 

Lista kroków z czasami wykonania operacji:

 

Krok Operacja Czas wykonania
K01: Czytaj n 1 × t1
K02: suma ← 0 1 × t2
K03: i ← 1 1 × t2
K04: Jeśli i > n, to idź do K09 (n + 1) × t4a dla jeśli ..., 1 × t4b dla idź do ...
K05: sumasuma + i n × t5
K06: ii + 1 n × t6
K08: Idź do K04 n × t4b
K09: Pisz suma 1 × t9
K10: Zakończ 1 × t10

 

Sumujemy czasy wykonania poszczególnych operacji otrzymując złożoność czasową. W kroku K04 są dwa czasy. Jeden dotyczy operacji jeśli..., która wykonywana jest zawsze o 1 razy więcej niż wynosi n, drugi czas dotyczy operacji idź do..., która wykonywana jest tylko jeden raz przy zakończeniu pętli.

 

T(n) = t1 + 2t2 +  (n + 1)t4a + t4b + nt5 + nt6 + nt4b + t9 + t10
T(n) = t1 + 2t2 +  (n + 1) t4a + (n + 1)t4b + n(t5 + t6) + t9 + t10
T(n) = (n + 1) (t4a + t4b) + n(t5 + t6) + t1 + 2t2 + t9 + t10

 

Teraz określmy następujące stałe, które określają czasy wykonania odpowiednich grup operacji algorytmu:

 

a = t4a + t4b
b = t5 + t6
c = t1 + 2t2 + t9 + t10

 

i otrzymujemy wzór na czasową złożoność obliczeniową algorytmu:

 

T(n) = a(n + 1) + bn + c
T(n) = an + a + bn + c

 

T(n) = (a + b)n + a + c

 

Ze wzoru tego widzimy wyraźnie, iż czas wykonania algorytmu jest liniowo zależny od ilości sumowanych liczb naturalnych - jeśli n wzrośnie dwa razy, to czas wykonania też wzrośnie w przybliżeniu dwukrotnie. Tak wyrażona złożoność obliczeniowa ma wymiar jednostek czasu, których użyto do pomiaru czasu wykonania poszczególnych operacji algorytmu na konkretnym komputerze.

 

Innym sposobem określenie złożoności czasowej jest wyznaczenie w algorytmie operacji dominującej i zliczenie liczby jej wykonań. Pozostałe operacje traktujemy jako nieistotne - tzn. ich czas wykonania jest pomijalnie mały w porównaniu z czasem wykonania wszystkich operacji dominujących. W naszym algorytmie taką operacją dominującą może na przykład jeden obieg pętli sumującej liczby naturalne.

 

T(n) = n

 

W uproszczeniu otrzymaliśmy podobny wynik do poprzedniego przykładu. Jednakże teraz złożoność czasowa nie posiada wymiaru czasu lecz określa liczbę operacji dominujących. Ten sposób jest bardziej ogólny, ponieważ uniezależnia wynik od konkretnego komputera - czy będzie to mały komputer PC, czy duży VAX, to należy wykonać n obiegów pętli. Czasy wykonań mogą być zupełnie inne, lecz własności tego algorytmu można przewidzieć na obu maszynach - liniowość czasu wykonania w funkcji liczby sumowań.

 


 

Przy konstruowaniu algorytmów często sięgamy do matematyki. Kolejne liczby naturalne tworzą ciąg arytmetyczny:

 

a1 = 1, d = 1

a2 = a1 + d = 1 + 1 = 2
a3 = a1 + 2d = 1 + 2 = 3
a4 = a1 + 3d = 1 + 3 = 4
...
an = a1 + (n - 1)d = 1 + n - 1 = n

 

Dla ciągu arytmetycznego suma n kolejnych wyrazów wyraża się wzorem:

 

 

W naszym ciągu mamy:

 

 

Zatem algorytm można uprościć do postaci:

 

Lista kroków z czasami wykonania operacji:

 

Krok Operacja Czas wykonania
K01: Czytaj n t1
K02: suma ← n(n + 1)/2 t2
K03: Pisz suma t3
K04: Zakończ t4

 

T(n) = t1 + t2 + t3 + t4,      niech a = t1 + t2 + t3 + t4

T(n) = a   - stały czas wykonania

 

Czas wykonania tego algorytmu nie zależy od wartości n, czyli jest stały. Taki wynik jest o niebo lepszy od poprzedniego.

 

Klasy złożoności

Przy analizie algorytmów często korzysta się z tzw. klas złożoności obliczeniowej (ang. computational complexity class), które określają rząd funkcji T(n). Jednym ze sposobów określania rzędu funkcji T(n) jest popularna notacja omikron (zwana także notacją dużego O) o następującej definicji:

 

Mówimy, iż T(n) = O(f(n))  (funkcja złożoności obliczeniowej T(n) jest rzędu funkcji f(n)) jeśli potrafimy znaleźć takie n0 ∈ N oraz takie c ∈ R, iż dla każdego n ≥ n0 prawdziwa jest nierówność:

 

T(n) ≤ cf(n)

 

 

Przykład:

Funkcja złożoności obliczeniowej wyraża się wzorem

 

T(n) = 5n - 4

 

Udowodnimy, iż T(n) = O(n). W tym celu musimy wskazać takie n0 i takie c, aby dla każdego n większego od n0 spełniona była nierówność:

 

5n - 4 ≤ cn

Wystarczy przyjąć:

 

n0 = 1
c = 5

 

Wtedy  5n - 4 < 5n, co jest spełnione dla wszystkich n ≥ 1. Udowodniliśmy w ten sposób, iż T(n) = O(n).

 

Przykład:

Funkcja złożoności obliczeniowej T(n) = 3n2 + 5n - 3. Należy wykazać, iż T(n) = O(n2).

Przyjmujemy n0 = 1 i c = 5. Wtedy, zgodnie z definicją notacji omikron, otrzymamy nierówność:


3n2 + 5n - 3 ≤ 5n2

 

Sprawdzamy, czy jest spełniona dla n ≥ n0.

 

Dla n = 1:  3n2 + 5n - 3  =   3 +  5 - 3 =   5 ≤ 5n2 =   5  - spełnione
Dla n = 2:  3n2 + 5n - 3  = 12 + 10 - 3 = 19 ≤ 5n2 = 20  - spełnione
Dla n = 3:  3n2 + 5n - 3  = 27 + 15 - 3 = 29 ≤ 5n2 = 45  - spełnione
Dla n = 4:  3n2 + 5n - 3  = 48 + 20 - 3 = 65 ≤ 5n2 = 80  - spełnione
...

 

Lewa strona nierówności rośnie wolniej od prawej, zatem nierówność będzie spełniona dla każdego n ≥ n0. Udowodniliśmy, iż T(n) = O(n2).

 

 



List do administratora Serwisu Edukacyjnego Nauczycieli I LO

Twój email: (jeśli chcesz otrzymać odpowiedź)
Temat:
Uwaga: ← tutaj wpisz wyraz  ilo , inaczej list zostanie zignorowany

Poniżej wpisz swoje uwagi lub pytania dotyczące tego rozdziału (max. 2048 znaków).

Liczba znaków do wykorzystania: 2048

 

W związku z dużą liczbą listów do naszego serwisu edukacyjnego nie będziemy udzielać odpowiedzi na prośby rozwiązywania zadań, pisania programów zaliczeniowych, przesyłania materiałów czy też tłumaczenia zagadnień szeroko opisywanych w podręcznikach.



   I Liceum Ogólnokształcące   
im. Kazimierza Brodzińskiego
w Tarnowie

©2017 mgr Jerzy Wałaszek

Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.