JADWIGA CHUDZICKA
1
MIARY ZŁOŻONOŚCI
MIARY ZŁOŻONOŚCI
OBLICZENIOWEJ
OBLICZENIOWEJ
JADWIGA CHUDZICKA
1
MIARY ZŁOŻONOŚCI
MIARY ZŁOŻONOŚCI
OBLICZENIOWEJ
OBLICZENIOWEJ
JADWIGA CHUDZICKA
2
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
3
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
4
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
5
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
6
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
7
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) = t
c
T(n) =
t
c
+ 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
t
c
. Analogiczny czas dla danych >= 1 jest równy
T(n) =
t
c
+ T(n – 1)
.
JADWIGA CHUDZICKA
8
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
9
T(n) =
t
c
+ T(n – 1)
T(n – 1) = t
c
+ T(n – 2)
T(n – 2) = t
c
+ T(n – 3)
.
.
.
T(1) =
t
c
+ T(0)
T(0) = t
c
Dodając stronami powyższe równania otrzymujemy:
T(n) + T(n – 1) + … + T(0) = (n + 1) t
c
+
+ T(n – 1) + T(n – 2) + … + T(0)
JADWIGA CHUDZICKA
10
Po zredukowaniu składników identycznych po
obu stronach równości, otrzymujemy
zależność:
T(n) =
(n + 1) t
c
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
t
c
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
11
Tego typu wynik dokładnych obliczeń jest
nazywany
złożonością praktyczną
algorytmu.
Funkcję taką oznacza się zwykle przez T.
ZŁOŻONOŚĆ PRAKTYCZNA
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) t
c
otrzymamy np.
T(n) =
(n + 4) t
c
JADWIGA CHUDZICKA
12
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?
ZŁOŻONOŚĆ TEORETYCZNA
(KLASA ALGORYTMU)
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
13
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
14
T(n)
O
7
7
O(1)
O(1)
5n +4
5n +4
O(n)
O(n)
n
n
2
2
– n +6
– n +6
O(n
O(n
2
2
)
)
2
2
n
n
+ n
+ n
2
2
-3
-3
O(2
O(2
n
n
)
)
ZŁOŻONOŚĆ PRAKTYCZNA
T(n)
I TEORETYCZNA
O
Interpretacja
JADWIGA CHUDZICKA
15
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.
W zapisie
n
2
2
– n +6
o wiele ważniejsza jest
funkcja kwadratowa niż liniowa zależność od
n
.
W zapisie
2
2
n
n
+ n
+ n
2
2
-3
-3
dominuje funkcja
dominuje funkcja
2
2
n
n
.
JADWIGA CHUDZICKA
16
PRZYKŁADY FUNKCJI
PRZYKŁADY FUNKCJI
O
O
Klasa
Klasa
O(1)
O(1)
oznacza, że liczba operacji
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
17
PRZYKŁADY FUNKCJI
PRZYKŁADY FUNKCJI
O
O
– c.d.
– c.d.
Klasa
Klasa
O(n)
O(n)
oznacza, że algorytm jest
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
18
PRZYKŁADY FUNKCJI
PRZYKŁADY FUNKCJI
O
O
– c.d.
– c.d.
Złożoność
Złożoność
O(log n)
O(log n)
jest lepsza od liniowej, co
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… log
10
10 = 1
ln 100 = 4,60… log
10
100 = 2
Jeszcze mniejszy wzrost złożoności obserwuje się
przy zmianie n ze 100 na 1000, np.
log
10
100 = 2, natomiast log
10
1000 = 3, a więc
wzrost tylko o 1,5.
JADWIGA CHUDZICKA
19
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
20
PRZYKŁADY FUNKCJI
PRZYKŁADY FUNKCJI
O
O
– c.d.
– c.d.
Klasa
Klasa
O(n
O(n
2
2
)
)
jest często spotykana w zadaniach
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(n
O(n
3
3
)
)
dobrym przykładem jest mnożenie
macierzy o rozmiarach n x n.
Algorytmy „kwadratowe” i wyższe nadają się raczej
dla małych wartości n.
JADWIGA CHUDZICKA
21
PRZYKŁADY FUNKCJI
PRZYKŁADY FUNKCJI
O
O
– c.d.
– c.d.
Klasa wykładnicza
Klasa wykładnicza
O(2
O(2
n
n
)
)
jest niekorzystna pod
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
22
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.