MIARY ZA
OŻONOŚCI
MIARY ZA
OŻONOŚCI
OBLICZENIOWEJ
OBLICZENIOWEJ
JADWIGA CHUDZICKA 1
Dokonując analizy algorytmów należy
wybrać właściwą miarę złożoności
obliczeniowej. Powinna być ona na
tyle reprezentatywna, aby
użytkownicy zarówno np. laptopa jak
i stacji roboczej o dużej mocy - jeśli
używają tego samego algorytmu -
mogli porozumieć się co do jego
sprawności obliczeniowej.
JADWIGA CHUDZICKA 2
Nie wystarczy stwierdzić, że algorytm jest
szybki, bo wykonał się w pół minuty.
Trzeba jeszcze wiedzieć, np.:

Jakiego komputera użył?
Jakiego komputera użył?

Jaka była liczba przetwarzanych
Jaka była liczba przetwarzanych
informacji?
informacji?

Jaka jest częstotliwość pracy zegara
Jaka jest częstotliwość pracy zegara
taktującego procesor?
taktującego procesor?

Czy algorytm był jedynym wykonującym się
Czy algorytm był jedynym wykonującym się
wówczas programem, a jeśli nie, to jaki
wówczas programem, a jeśli nie, to jaki
miał priorytet?
miał priorytet?
itd&
itd&
W ten sposób daleko nie zajdziemy.
W ten sposób daleko nie zajdziemy.
JADWIGA CHUDZICKA 3
Potrzebna jest miara uniwersalna, niemająca
nic wspólnego ze szczegółami natury 
powiedzmy  sprzętowej.
Parametrem najczęściej decydującym o czasie
wykonania określonego algorytmu jest rozmiar
danych n, z którymi ma on do czynienia.
Pojęcie rozmiaru danych jest tu wieloznaczne: w
sortowaniu tablicy będzie to rozmiar tablicy, dla funkcji
silnia  wielkość danej wejściowej.
JADWIGA CHUDZICKA 4
Uogólniając, można powiedzieć, że
rozmiar danych n jest to
najbardziej znaczący parametr
algorytmu, wpływający na czas jego
wykonania.
JADWIGA CHUDZICKA 5
Ilustracja złożoności na przykładzie
Ilustracja złożoności na przykładzie
funkcji silnia
funkcji silnia
Do wyznaczenia silni można użyć np. funkcji w C++
int silnia (int n)
{
if (n==0)
return 1;
Else
return n * silnia(n  1);
}
JADWIGA CHUDZICKA 6
Upraszczając, można przyjąć, że najbardziej
czasochłonną operacją jest tutaj instrukcja
porównania if. Przy tym założeniu czas wykonania
programu można zapisać również rekurencyjnie jako:
T(0) = tc
T(n) = tc + T(n  1) dla n>=1
tzn. dla danej wejściowej równej zero czas wykonania
funkcji, oznaczany jakoT(0), równa się czasowi
wykonania jednej instrukcji porównania, oznaczonej
przez tc. Analogiczny czas dla danych >= 1 jest równy
T(n) = tc + T(n  1).
JADWIGA CHUDZICKA 7
Taki zapis czasu obliczeń jest w praktyce
nieprzydatny, gdyż nie można od razu
powiedzieć, ile czasu zajmie wyznaczenie np.
silnia(50). Chcielibyśmy mieć jakąś funkcję
nierekurencyjną wyliczającą czas T(n).
W tym celu rozpiszmy równania na T(n) dla
wszystkich argumentów: 0, 1, 2, & , n.
JADWIGA CHUDZICKA 8
T(n) = tc + T(n  1)
T(n  1) = tc + T(n  2)
T(n  2) = tc + T(n  3)
.
.
.
T(1) = tc + T(0)
T(0) = tc
Dodając stronami powyższe równania otrzymujemy:
T(n) + T(n  1) + & + T(0) = (n + 1) tc +
+ T(n  1) + T(n  2) + & + T(0)
JADWIGA CHUDZICKA 9
Po zredukowaniu składników identycznych po
obu stronach równości, otrzymujemy
zależność:
T(n) = (n + 1) tc
Otrzymaliśmy prostą funkcję, która pokazuje, w jaki
sposób rozmiar danej wejściowej wpływa na liczbę
instrukcji porównań wykonywanych przez program 
czyli de facto na czas wykonania algorytmu. Znając
bowiem parametr tc i wartość n, można dokładnie
określić, w ciągu ilu sekund czy innych jednostek
czasowych wykona się program na danym komputerze.
JADWIGA CHUDZICKA 10
ZA
OŻONOŚĆ PRAKTYCZNA
Tego typu wynik dokładnych obliczeń jest
nazywany złożonością praktyczną algorytmu.
Funkcję taką oznacza się zwykle przez T.
W praktyce rzadko interesuje nas aż tak dokładny
wynik. Dla odpowiednio dużych n niewiele się
zmieni, jeśli zamiast T(n) = (n + 1) tc
otrzymamy np. T(n) = (n + 4) tc
JADWIGA CHUDZICKA 11
ZA
OŻONOŚĆ TEORETYCZNA
(KLASA ALGORYTMU)
Z powyższego powodu bardziej interesuje nas, jaki
typ funkcji matematycznej, występującej w
zależności określającej złożoność praktyczną
programu, odgrywa w niej najważniejszą rolę,
wpływając najsilniej na czas wykonywania programu?
Tę poszukiwaną funkcję będziemy nazywać
złożonością teoretyczną lub klasą algorytmu i
to ona występuje najczęściej w opisach algorytmów.
Najczęściej używana tego rodzaju funkcja jest
oznaczana literą O.
JADWIGA CHUDZICKA 12
W jaki sposób otrzymać funkcję określającą klasę
algorytmu? Stosowane są dwa podejścia:

można opierać się na pewnych twierdzeniach
matematycznych i stosować je w odpowiednich
sytuacjach;

można dochodzić do prawidłowego wyniku
metodą intuicyjną.
Oba podejścia prowadzą zwykle do tego samego
rezultatu, a metoda intuicyjna jest przy tym szybka i
przystępniejsza, co będzie widoczne w dalszych
przykładach. Będziemy uzyskiwać złożoność
teoretyczną z równań określających złożoność
praktyczną.
JADWIGA CHUDZICKA 13
ZA
OŻONOŚĆ PRAKTYCZNA T(n) I TEORETYCZNA O
T(n) O
7 O(1)
7 O(1)
5n +4 O(n)
5n +4 O(n)
n2  n +6 O(n2)
n2  n +6 O(n2)
2n + n2 -3 O(2n )
2n + n2 -3 O(2n )
Interpretacja
JADWIGA CHUDZICKA 14
W pierwszym przykładzie liczba operacji stała
(=7), niezależna od rozmiarów problemu.
W zapisie 5n +4, wynik nie ulegnie znaczącej
zmianie przy pominięciu stałych.
2
W zapisie n2  n +6 o wiele ważniejsza jest
funkcja kwadratowa niż liniowa zależność od n.
W zapisie 2n + n2 -3 dominuje funkcja 2n.
2n + n2 -3 dominuje funkcja 2n
JADWIGA CHUDZICKA 15
PRZYKA
ADY FUNKCJI O
PRZYKA
ADY FUNKCJI O

Klasa O(1) oznacza, że liczba operacji
Klasa O(1)
wykonywanych w algorytmie jest niezależna od
rozmiarów problemu (niekoniecznie mała!).
Algorytmy tej klasy niekoniecznie muszą być
trywialne. Można wskazać złożony przykład
wyszukiwania oparty na metodzie transformacji
kluczowej (hashing). Przy dobrej funkcji H można
dotrzeć do poszukiwanego rekordu w mniej
więcej tym samym czasie, niezależnie od
wielkości zbioru do przeszukania.
JADWIGA CHUDZICKA 16
PRZYKA
ADY FUNKCJI O  c.d.
PRZYKA
ADY FUNKCJI O  c.d.

Klasa O(n) oznacza, że algorytm jest
Klasa O(n)
wykonywany w czasie proporcjonalnym do
rozmiaru problemu.
Jest to prosta zależność liniowa, gdzie każdej z n
danych algorytm musi poświęcić pewien czas na
wykonanie swoich obliczeń.
Przykładem takiego algorytmu może być
przetwarzanie sekwencyjne ciągu znaków,
obsługa kolejki itp.
JADWIGA CHUDZICKA 17
PRZYKA
ADY FUNKCJI O  c.d.
PRZYKA
ADY FUNKCJI O  c.d.

Złożoność O(log n) jest lepsza od liniowej, co
Złożoność O(log n)
oznacza, że jeśli rozmiar problemu rośnie
geometrycznie (np. o rząd wielkości z 10 na 100), to
wzrost złożoności będzie arytmetyczny (w tym
przykładzie dwukrotny niezależnie od podstawy
logarytmu). Porównajmy np. dla podstawy e i 10:
ln 10 = 2,30& log1010 = 1
ln 100 = 4,60& log10100 = 2
Jeszcze mniejszy wzrost złożoności obserwuje się
przy zmianie n ze 100 na 1000, np.
log10100 = 2, natomiast log101000 = 3, a więc
wzrost tylko o 1,5.
JADWIGA CHUDZICKA 18
Jeśli n rośnie niezbyt szybko, to algorytm
zwalnia, ale nie drastycznie.
Złożoność logarytmiczną można spotkać
np. w pewnym algorytmie przeszukiwania
posortowanej tablicy, gdzie w każdym
kroku algorytmu pomija się część danych.
JADWIGA CHUDZICKA 19
PRZYKA
ADY FUNKCJI O  c.d.
PRZYKA
ADY FUNKCJI O  c.d.

Klasa O(n2) jest często spotykana w zadaniach
Klasa O(n2)
arytmetycznych i kombinatorycznych, gdzie mamy
do czynienia z regułą  każdy z każdym .
Przykładem może być dodawanie macierzy o
rozmiarach n x n.

Dla klasy O(n3) dobrym przykładem jest mnożenie
O(n3)
macierzy o rozmiarach n x n.
Algorytmy  kwadratowe i wyższe nadają się raczej
dla małych wartości n.
JADWIGA CHUDZICKA 20
PRZYKA
ADY FUNKCJI O  c.d.
PRZYKA
ADY FUNKCJI O  c.d.

Klasa wykładnicza O(2n) jest niekorzystna pod
Klasa wykładnicza O(2n)
względem złożoności, ale jeśli mimo
szybkiego wzrostu złożoności wraz ze
wzrostem rozmiaru problemu, wyniki w
konkretnych przypadkach uzyskuje się w
sensownym dla użytkownika czasie, to w
praktyce można również takie algorytmy
wykorzystywać.
JADWIGA CHUDZICKA 21
Poza przytoczonymi poglądowymi informacjami
na temat klasy O można podać jej formalną
definicję i pewne własności.
Klasa O (wg def. jest to zbiór funkcji) ma
charakter wielkości asymptotycznej, pozwalającej
wyrazić w postaci arytmetycznej wielkości z góry
nieznane w postaci analitycznej.
Samo istnienie tej notacji pozwala na znaczne
uproszczenie wielu dociekań matematycznych, w
których dokładna znajomość rozważanych
wielkości nie jest konieczna.
JADWIGA CHUDZICKA 22