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.