Złożoność obliczeniowa czasowa 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) = 4n2 - 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, wyjmij jedno jabłko z kosza, obejrzyj je, jeśli jest robaczywe, to zakończ. Inaczej odłóż je na bok i wróć do początku.

 

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
Krok 1: Czytaj n 1 × t1
Krok 2: suma ← 0 1 × t2
Krok 3: i ← 1 1 × t2
Krok 4: Jeśli i > n, to idź do K08 (n + 1) × t4a dla jeśli ..., 1 × t4b dla idź do ...
Krok 5: sumasuma + i n × t5
Krok 6: ii + 1 n × t6
Krok 7: Idź do K04 n × t4b
Krok 8: Pisz suma 1 × t8
Krok 9: Zakończ 1 × t9

 

Sumujemy czasy wykonania poszczególnych operacji otrzymując złożoność czasową. W kroku nr 4 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 + t8 + t9
T(n) = t1 + 2t2 +  (n + 1) t4a + (n + 1)t4b + n(t5 + t6) + t8 + t9
T(n) = (n + 1) (t4a + t4b) + n(t5 + t6) + t1 + 2t2 + t8 + t9

 

Teraz określmy następujące stałe, które odnoszą się do czasów wykonania odpowiednich grup operacji algorytmu:

 

ta = t4a + t4b
tb = t5 + t6
tc = t1 + 2t2 + t9 + t10

 

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

 

T(n) = ta(n + 1) + tbn + tc
T(n) = tan + ta + tbn + tc

 

T(n) = (ta + tb)n + ta + tc

 

Wzór da się dalej uprościć wprowadzając kolejne stałe:

 

tab = ta + tb
tac = ta + tc
 

Wtedy:

 

T(n) = tabn + tac

 

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 (dla dużych n czas tac można pominąć, gdyż jest jednostkowy). 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
Krok 1: Czytaj n t1
Krok 2: suman(n + 1)/2 t2
Krok 3: Pisz suma t3
Krok 4: Zakończ t4

 

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

T(n) = ta   - 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. Wniosek: często opłaca się rozważyć dany problem matematycznie.

 

Klasy złożoności

Przy analizie algorytmów 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 tej funkcji jest popularna notacja omikron (zwana także notacją dużego O) o następującej definicji:

 

Mówimy, że T(n) = O(f(n))  (funkcja złożoności obliczeniowej T(n) jest rzędu funkcji f(n)) jeśli potrafimy znaleźć takie n0N oraz takie cR, iż dla każdego nn0 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 nn0.

 

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 = 39 ≤ 5n2 = 45  - spełnione
Dla n = 4:  3n2 + 5n - 3  = 48 + 20 - 3 = 65 ≤ 5n2 = 80  - spełnione
...

 

Przy wzroście n lewa strona nierówności rośnie wolniej od prawej, zatem nierówność będzie spełniona dla każdego nn0. Wykazaliśmy, że T(n) = O(n2).

 

Klasę złożoności obliczeniowej algorytmu można rozpoznać niekiedy po jego cechach charakterystycznych:

 

O(1) - stała klasa czasowej złożoności obliczeniowej

Algorytm wykonuje stałą liczbę operacji bez względu na rozmiar danych n.

O(n) - liniowa klasa czasowej złożoności obliczeniowej

Algorytm wykonuje stałą liczbę operacji dla każdej danej n.

O(n2) - kwadratowa klasa czasowej złożoności obliczeniowej

Dla każdej danej n algorytm wykonuje proporcjonalną do n liczbę operacji.

 

Oprócz powyższych istnieją również inne charakterystyczne klasy złożoności obliczeniowej, o których dowiesz się w dalszej części kursu informatyki (O(log n) - logarytmiczna, O(n log n) - liniowo logarytmiczna, O(2n) O(n!) - wykładnicza).

 

Klasy pamięciowej złożoności obliczeniowej określamy podobnie, w zależności od liczby zajętych przez algorytm komórek pamięci:

O(1) - stała klasa pamięciowej złożoności obliczeniowej

Algorytm zużywa stałą liczbę komórek pamięci bez względu na rozmiar danych n.

O(n) - liniowa klasa pamięciowej złożoności obliczeniowej

Algorytm zużywa liczbę komórek pamięci proporcjonalną do n.

O(n2) - kwadratowa klasa pamięciowej złożoności obliczeniowej

Dla każdej danej n algorytm zużywa liczbę komórek pamięci proporcjonalną do n.

 

Podobnie jak złożoność obliczeniowa, klasa złożoności obliczeniowej może być optymistyczna, typowa lub pesymistyczna.

Znajomość klas złożoności obliczeniowej czasowej i pamięciowej dla różnych algorytmów pozwala informatykowi przewidywać zachowanie się tych algorytmów dla różnych zestawów danych oraz dobierać algorytmy dla określonych sytuacji. Dlatego jest to jedno z kluczowych pojęć algorytmiki.

 

Zadanie

Wyznacz czasową złożoność obliczeniową oraz klasę czasowej złożoności obliczeniowej dla następującego algorytmu:

 

Wejście:

    n - ilość liczb w tablicy
    T[ ] - tablica zawierająca n liczb
Wyjście:

    s - wynik pracy algorytmu

Dane pomocnicze:

       i,j - indeksy elementów
 

Krok 1: s ← 0
Krok 2: i ← 0
Krok 3: Jeśli i = n - 10, to zakończ
Krok 4: j0
Krok 5: Jeśli j = 10, to idź do kroku 9
Krok 6: ss + T[i + j]
Krok 7: jj + 1
Krok 8: Idź do kroku 5
Krok 9: ii + 1
Krok 10: Idź do kroku 3

 



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.