Autor artykułu: mgr Jerzy Wałaszek, wersja 1.0
©2008 mgr
Jerzy Wałaszek
I LO w Tarnowie
|
Autor artykułu: mgr Jerzy Wałaszek, wersja 1.0 |
©2008 mgr
Jerzy Wałaszek
|
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.
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.
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: | suma ← suma + i | n × t5 |
| K06: | i ← i + 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.
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).
 | I Liceum Ogólnokształcące |
Pytania proszę przesyłać na adres email: i-lo@eduinf.waw.pl
W artykułach serwisu są używane cookies. Jeśli nie chcesz ich otrzymywać,
zablokuj je w swojej przeglądarce.
Informacje dodatkowe