Prezentowane materiały są przeznaczone dla uczniów szkół ponadgimnazjalnych. Autor artykułu: mgr Jerzy Wałaszek,  wersja1.0

©2010 mgr Jerzy Wałaszek I LO w Tarnowie

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:

• czas (ang. time)
• pamięć (ang. memory, space)

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) = 4n² - 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:

• T_O(n) - optymistycznej (ang. optimistic)
• T_A(n) - średniej (ang. average)
• T_W(n) - pesymistycznej (ang. worst)

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:
   T_o(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:
   T_w(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 ⁿ/₂ teście:
   T_A(n) = ⁿ/₂ - 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:

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) = t₁ + 2t₂ +  (n  + 1)t_4a + t_4b + nt₅ + nt₆ + nt_4b + t₈ + t₉
T(n) = t₁ + 2t₂ +  (n  + 1) t_4a + (n  + 1)t_4b + n(t₅ + t₆) + t₈ + t₉
T(n) = (n  + 1) (t_4a + t_4b) + n(t₅ + t₆) + t₁ + 2t₂ + t₈ + t₉

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

t_a  = t_4a + t_4b
t_b  = t₅ + t₆
t_c  = t₁ + 2t₂ + t₉ + t₁₀

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

T(n) = t_a(n  + 1) + t_bn  + t_c
T(n) = t_an  + t_a  + t_bn  + t_c

T(n) = (t_a  + t_b)n  + t_a  + t_c

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

t_ab  = t_a  + t_b
t_ac  = t_a  + t_c
 

Wtedy:

T(n) = t_abn  + t_ac

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 t_ac  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:

a₁ = 1, d  = 1

a₂ = a₁ + d  = 1 + 1 = 2
a₃ = a₁ + 2d  = 1 + 2 = 3
a₄ = a₁ + 3d  = 1 + 3 = 4
...
a_n  = a₁ + (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:

T(n) = t₁ + t₂ + t₃ + t₄,      niech t_a  = t₁ + t₂ + t₃ + t₄

T(n) = t_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. 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 n₀ ∈ N  oraz takie c  ∈ R, iż dla każdego n  ≥ n₀ 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 n₀ i takie c, aby dla każdego n  większego od n₀ spełniona była nierówność:

5n  - 4 ≤ cn

Wystarczy przyjąć:

n₀ = 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) = 3n² + 5n  - 3. Należy wykazać, iż T(n) = O(n²).

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

3n² + 5n  - 3 ≤ 5n²

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

Dla n  = 1:  3n² + 5n  - 3  =   3 +  5 - 3 =   5 ≤ 5n² =   5  - spełnione
Dla n  = 2:  3n² + 5n  - 3  = 12 + 10 - 3 = 19 ≤ 5n² = 20  - spełnione
Dla n  = 3:  3n² + 5n  - 3  = 27 + 15 - 3 = 39 ≤ 5n² = 45  - spełnione
Dla n  = 4:  3n² + 5n  - 3  = 48 + 20 - 3 = 65 ≤ 5n² = 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 n  ≥ n₀. Wykazaliśmy, że T(n) = O(n²).

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(n²) - 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(2ⁿ) 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(n²) - 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
 

---

I Liceum Ogólnokształcące    im. Kazimierza Brodzińskiego w Tarnowie ©2026 mgr Jerzy Wałaszek

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

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