1

Projektowanie i analiza algorytmów

Design and analysis of computer algorithms

Analiza i projektowanie algorytmów

Analiza algorytmów pozwala odpowiedzieć na pytania:

Czy dany problem może być rozwiązany na komputerze w dostępnym czasie i

określonej pamięci ?

Który algorytm zastosować w danych okolicznościach ?

Czy istnieje lepszy algorytm (czy jest on optymalny) ?

Jak uzasadnić, że dany algorytm rozwiązuje postawione zadanie ?

ASD

LJ

S

2

Analiza algorytmów

Aspekty analizy algorytmów:

Poprawności semantycznej algorytmu.

Złożoności obliczeniowej: czasowej, pamięciowej.

ASD

LJ

S

Analiza algorytmów uwzględnia: poprawność semantyczną, czas działania, zajętość
pamięci, optymalność, okoliczności użycia algorytmu.

Określanie poprawności algorytmu:

1.

Metoda empiryczna (testowanie programu).

2.

Formalne dowodzenie poprawności algorytmu.

Analiza w aspekcie złożoności obliczeniowej (czasowej i przestrzennej) związana
jest z tzw. kosztem algorytmu. Projektowanie algorytmu polega na minimalizacji
tego kosztu.

Metody projektowania algorytmów

Metody projektowania algorytmów:

Meoda „dziel i zwyciężaj” (

divide-and-conquer strategy

).

Programowanie dynamiczne (

dynamic programming

).

Rekurencja (

recursive approach

).

Metoda przyrostowa (algorytmy konstrukcyjne) (

constructive method

).

Metoda zachłanna (

greedy approach

).

Metody aproksymacyjne (

aproximation algorithms

).

Metody zrównoleglenia algorytmów (

parallel algorithms

).

ASD

LJ

S

3

Metoda „dziel i zwyciężaj”

Charakterystyka metody:



Podział problemu wyjściowego na mniejsze podproblemy tej samej postaci
ale mniejszego rozmiaru,



Rozwiązanie podproblemów, na podstawie których wyznaczane jest

rozwiązania końcowe,



Stosowana w połączeniu z rekurencją,



Przykład podejścia zstępującego w projektowaniu (top down),



Rozwiązywane przykładowe problemy: sortowanie „quicksort”, sortowanie

„przez scalanie”, silnia, przeszukiwanie ciągu itd.

ASD

LJ

S

Metoda programowania dynamicznego

Charakterystyka metody:



Rozszerzenie i optymalizacja strategii „dziel i zwyciężaj”,



Podział problemu na mniejsze podproblemy (w tym kontekście metoda jest

podobna do metody „dziel i zwyciężaj”), które są najpierw rozwiązywane a

wyniki przechowywane (np. w tablicy),



Wykorzystanie przechowywanych rozwiązań podproblemów do

konstruowania rozwiązania końcowego,



Przykład podejścia wstępującego w projektowaniu (

bottom-up

),



Rozwiązywane problemy: ciąg fibonacciego, dwumian Newtona, zagadnienia

najkrótszej drogi w gafie, itd.

ASD

LJ

S

4

Złożoność obliczeniowa algorytmów

Computational Complexity

Hartmanis J., Stearns R. „On the Computational
Complexity of Algorithms”, 1965)

Złożoność obliczeniowa

ASD

LJ

S

Zakładamy, że rozpatrywane algorytmy realizowane są na maszynie RAM (

Random

Access Machine

) - koncepcja maszyny Neumanna (

Stored program concept

).

Cechy maszyny RAM:

1.

Rozkazy wykonywane są sekwencyjnie (

pobierz-dekoduj-wykonaj rozkaz

).

2.

Zbiór rozkazów zawiera rozkazy przesłań, arytmetyczne, logiczne,
porównania.

Cele analizy czasowej algorytmu:

1.

Porównanie różnych algorytmów rozwiązujących te same problemy.

2.

Przewidywanie wydajności algorytmów w nowym środowisku obliczeniowym.

3.

Określenie czasowych wartości parametrów algorytmów.

Miara porównania algorytmów powinna być niezależna od: komputera, języka
programowania, systemu operacyjnego, umiejętności programisty, szczegółów
implementacji.

5

Złożoność obliczeniowa

Podstawowe rodzaje złożoności.

Złożoność czasowa (

time complexity, running time

):

-

czasu wykonania wyrażony w standardowych jednostkach czasu lub
liczbie cykli procesora (niemożliwe na etapie algorytmu i pseudokodu),

-

czasu wykonania wyrażany w ilościach tzw. operacji dominujących
(upraszcza analizę).

Złożoność pamięciową (

space complexity

):

-

zapotrzebowanie na pamięć mierzone w: B, kB, MB, GB, TB,

-

ilość użytych zmiennych typów prostych np. integer lub real.

ASD

LJ

S

Czasowa złożoność obliczeniowa - funkcja określająca czas potrzebny do
wykonania algorytmu dla konkretnych danych.

Złożoność pamięciowa - funkcja określająca liczbę komórek pamięci potrzebnych
do wykonania algorytmu dla konkretnych danych.

Operacje podstawowe

Typowe operacje elementarne (podstawowe,

basic operations

):



Operacje arytmetyczne, logiczne, relacyjne,



Podstawienie,



Indeksowanie, odwołanie do pola struktury,



Inicjalizacja wywołania funkcji,



Przekazywanie wartości do funkcji,



Operacje we/wy,



„Wizyta” w węźle, przejście po krawędzi (algorytmy grafowe).

Przykłady operacji, które nie są elementarnymi to instrukcje: WHILE, REPEAT, FOR.

ASD

LJ

S

6

Rozmiar danych wejściowych

Instancja problemu (

problem instant

) - zestaw danych wejściowych.

Instancje problemu rozróżnia się ze względu na: rozmiar egzemplarza danych
(najczęściej liczbę danych określonych typów) oraz inne właściwości (np.
początkowe uporządkowanie elementów).

Określając bardziej formalnie, rozmiar danych wejściowych wyrażanych liczbą n jest
to liczba bitów potrzebnych do jej reprezentowania w kodzie NBC (

Natural Binary

Code

) naturalnym kodzie binarnym.

ASD

LJ

S

Rozmiar danych wejściowych (

input size, size of the input

) - liczba pojedynczych danych

wchodzących w skład struktury danych. Liczbę tą najczęściej oznaczmy przez n (w
niektórych przypadkach wymaga doprecyzowania).

Dla wartości n, liczba litów wynosi

lgn+1, n=100, 1100100, lg100+1 → 7 bitów.

x „podłogą” liczby rzeczywistej x∈R nazywamy największą liczbę całkowitą nie
większą niż x.

Rozmiar danych wejściowych

Rozmiar danych wejściowych (przykłady).

ASD

LJ

S

1.

W problemie sortowania ciągu skończonego a

1

a

2

, ... , a

n

rozmiarem danych

jest liczba n.

2.

W przypadku przetwarzania n-wierszowej i m-kolumnowej tablicy rozmiarem

danych jest liczba n* m.

3.

Dla algorytmów grafowych do okreslenia rozmiaru danych wejściowych

można użyć liczby wierzcholków i liczby łuków, występujacych w tym grafie.

4.

W algorytmie wyznaczania n-tego wyrazu ciągu Fibonacciego n będzie

rozmiarem danych i jednocześnie daną wejściową.

7

Złożoność obliczeniowa

Wyznaczanie czasowej złożoności obliczeniowej algorytmu.

Zakładamy, że czas działania algorytmu jest proporcjonalny do liczby wykonań
poszczególnych instrukcji zawartych wewnątrz kolejnych pętli.

ASD

LJ

S

Przykład. Wyznaczanie sumy trzecich potęg n najmniejszych liczb całkowitych.

Sum poteg(n)

liczba wykonań

{

1.

s=0;

1

2.

x=1;

1

3.

WHILE(x

≤n){

(n+1)

4.

y=x*x*x;

n

5.

s=s+y;

n

6.

x=x+1;

n

}

7.

return(s);

1

}

Funkcja czasowej złożoności algorytmu T(n) (liczba wykonań poszczególnych
instrukcji): T(n) = 4n + 4

Złożoność obliczeniowa

Przykład. Dany jest ciąg n liczb całkowitych. Należy wyznaczyć początek i koniec
fragmentu podciągu, dla którego suma elementów jest największa.

ASD

LJ

S

Max pciag V1(A,n,p,k)
//A-tablica indeksowana od 1 do n

liczba wykonań

{

maxsum=MinInt;

1

p=1;

1

k=1;

1

FOR(i=1,2,…,n)

n

FOR(j=i,i+1,…,n){

(n-i+1)

asum=0;

J(n)

FOR (k=i,i+1,…,j)

(j-i+1)

asum=asum+A[k];

K(n)

IF (asum>maxsum){

J(n)

maxsum=asum;

J(n)

p=i;

J(n)

k=j;

J(n)

}

}

return(maxsum,p,k);

1

}

8

Złożoność obliczeniowa

Liczba operacji elementarnych w algorytmie Max pciag V1 zależy od:

ASD

LJ

S



Rozmiaru danych wejściowych n (liczba iteracji poszczególnych pętli).



Wartości danych (spełnienia warunku: asum > maxsum).

Liczba wykonań instrukcji w pętli po k:

n

n

n

i

n

i

n

i

j

n

K

n

i

n

i

j

n

i

j

i

k

n

i

j

n

i

3

1

2

1

6

1

2

)

2

)(

1

(

)

1

(

1

)

(

2

3

1

1

1

+

+

=

+

−

+

−

=

+

−

=

=

∑

∑

∑

∑

∑

∑

=

=

=

=

=

=

Liczba wykonań instrukcji w pętli po j:

n

n

n

n

i

n

n

J

n

i

n

i

j

n

i

2

1

2

1

2

)

1

(

)

1

(

1

)

(

2

1

1

+

=

+

=

+

−

=

=

∑

∑

∑

=

=

=

Złożoność pesymistyczna:

4

6

17

3

6

1

1

)

(

)

(

5

3

)

(

2

3

+

+

+

=

+

+

+

=

n

n

n

n

K

n

J

n

T

Złożoność obliczeniowa

ASD

LJ

S

Max pciag V2(A,n,p,k)

//A-tablica indeksowana od 1 do n

liczba wykonań

{

maxsum=MinInt;

1

p=1;

1

k=1;

1

FOR(i=1,2,…,n){

n

asum=0;

I(n)

FOR (k=i,i+1,…,n) {

(n-i+1)

asum=asum+A[j];

J(n)

IF (asum>maxsum){

J(n)

maxsum=asum;

J(n)

p=i;

J(n)

k=j;

J(n)

}

}

}
return(maxsum,p,k;

1

}

9

Złożoność obliczeniowa

ASD

LJ

S

Liczba wykonań instrukcji w pętli wewnętrznej:

J(n) – liczba obrotów pętli po j.

I(n) – liczba obrotów pętli po i.

Złożoność pesymistyczna:

n

n

n

n

i

n

J

n

i

n

i

j

n

i

2

1

2

1

2

)

1

(

1

)

(

2

1

1

+

=

+

=

=

=

∑

∑

∑

=

=

=

n

n

I

=

)

(

4

2

7

2

5

1

)

(

5

)

(

3

)

(

2

+

+

=

+

+

+

=

n

n

n

J

n

I

n

T

Złożoność obliczeniowa

ASD

LJ

S

Max pciag V3(A,n,p,k)

//A-tablica indeksowana od 1 do n

liczba wykonań

{

maxsum=MinInt;

1

p=1;

1

k=1;

1

i=1;

1

asum=0;

1

FOR(j=1,2,…,n){

n

asum=asum+A[j];

J(n)

IF (asum>maxsum){

J(n)

maxsum=asum;

J(n)

p=i;

J(n)

k=j;

J(n)

}

IF (asum < 0){

J(n)

i=j+1;

J(n)

asum=0;

J(n)

}

}
return(maxsum,p,k;

1

}

J(n) – liczba obrotów

pętli po j.

J(n) = n

6

8

)

(

+

= n

n

T

10

Złożoność obliczeniowa

ASD

LJ

S

Rozmiar
problemu n

Algorytm
Max pciag V1

Złożoność czasowa (liczba elementarnych operacji)

Algorytm
Max pciag V2

Algorytm
Max pciag V3

10

500

300

100

10

2

200 10

3

25 10

3

10

3

10

3

2 10

8

2.5 10

6

8 10

3

10

4

1.5 10

11

2.5 10

8

8 10

4

10

5

1.5 10

14

2.5 10

9

8 10

5

Porownanie czasów wykonania algorytmów

Złożoność obliczeniowa

ASD

LJ

S

Rozmiar problemu
n

Algorytm
Max pciag V1

Złożoność czasowa (w jednostkach czasowych)

Algorytm
Max pciag V2

Algorytm
Max pciag V3

10

0.5 ms

0.3 ms

0.1 ms

10

2

0.2 s

25 ms

1 ms

10

3

200 s

2.5 s

8 ms

10

4

45 godz.

5 min

0.8 ms

10

5

4.5 lat

50 min

0.8 s

Założony czas wykonywania elementarnej operacji wynosi 10

-6

s.

Porownanie czasów wykonania algorytmów

Konwersja sekund

10

2

s

→ 2 min

10

6

s

→ 1,5 tyg.

10

9

s

→ 30 lat

10

4

s

→ 3 godz.

10

8

s

→ 3 lata

10

10

s

→ 300 lat

11

Złożoność obliczeniowa

ASD

LJ

S

Rozmiar problemu
n

Algorytm
Max pciag V1

Złożoność czasowa (liczba elementarnych operacji)

Algorytm
Max pciag V2

Algorytm
Max pciag V3

10

0.5

µs

0.3

µs

0.1

µs

10

2

0.2 ms

0.025 ms

0.001 ms

10

3

0.2 s

2.5 ms

0.008 ms

10

4

3 min

0.25 s

0.08 ms

10

5

45 godz

2.5 s

0.8 ms

Porownanie czasów wykonania algorytmów

Założony czas wykonywania elementarnej operacji wynosi 10

-9

s.

Złożoność obliczeniowa

ASD

LJ

S

Rozmiar
problemu n

Algorytm
Max pciag V1

Złożoność czasowa (liczba elementarnych operacji)

Algorytm
Max pciag V2

Algorytm
Max pciag V3

10

0.5 ns

0.3 ns

0.1 ns

10

2

0.2 µs

25 ns

1 ns

10

3

0.2 m s

2.5 µs

8 ns

10

4

0.15 s

0.25 ms

80 ns

10

5

3 min

2.5 ms

0.8 µs

Porownanie czasów wykonania algorytmów

Założony czas wykonywania elementarnej operacji wynosi 10

-12

s.

12

Operacje dominujące

O złożoności czasowej algorytmu decydują operacje, które zwykle umieszczone są
w najbardziej wewnętrznej pętli.
Operacje takie nazywamy dominującymi (

dominant operations

).

ASD

LJ

S

Liczba operacji dominujących jest:

1.

Proporcjonalna do liczby wszystkich operacji algorytmu.

2.

Rzędu liczby wszystkich operacji.

3.

Proporcjonalna do czasu działania programu implementującego algorytm.

Problem

Operacja

Wyszukiwanie elementu x na liście

Porównywanie x z pozycją na liście

Mnożenie dwóch macierzy

Mnożenie dwóch liczb typu real

Sortowanie liczb

Porównywanie dwóch liczb, zamiana liczb

Trawersowanie grafu

Operacja na węźle, krawędzi

13

Asymptotyczna złożoność obliczeniowa

Notacje asymtotyczne

(Asymptotic notation, Order notation)

ASD

LJ

S

Notacje asymtotyczne

Asymptotyczne ograniczenie górne (

asymptotic upper bound

).

O-notacja.

Funkcja f(n) jest co najwyżej rzędu g(n) ( f(n)=O(g(n)) ) jeżeli:

(

∃ c>0 ) (∃ n

0

≥ 0 ) ∀ n ≥ n

0

zachodzi f(n)

≤ c g(n).

f(n) =O(g(n)) gdy lim

n

→∞

f(n)/g(n) = 0.

Inna definicja O-notacji:

f(n) =O(g(n))

≡ lim

n

→∞

sup

f(n)/g(n) < ∞

Paul Bachman (1892)

g(n)

≠ O(f(n)).

ASD

LJ

S

14

Notacje asymtotyczne

Symbol O(g(n)) oznacza zbiór funkcji f: N

→R

+

zdefiniowany następująco:

O( g(n) ) = {f

∈ R

+

: istnieje taka stała c>0 i n

0

∈N, że f(n)≤c g(n) dla

każdego n > n

0

}

Równoważne zapisy: f(n)=O(g(n)), f

∈O(g(n)).

Sens notacji O polega na istnieniu „asymptotycznego ograniczenia górnego”,

pozwalającego oszacować od góry wartości funkcji f przez wartości funkcji g.

ASD

LJ

S

Notacje asymtotyczne

1. f(n) = n

2

/2 = O(n

3

)

ASD

LJ

S

0

2

1

lim

2

/

lim

3

2

=

=

∞

→

∞

→

n

n

n

n

n

2.

f(n) = nlogn = O(n

2

)

log

b

a = log

c

a / log

c

b

0

2

ln

/

1

lim

2

ln

ln

lim

log

lim

2

=

=

=

∞

→

∞

→

∞

→

n

n

n

n

n

n

n

n

n

Wniosek:

nlogn = O(n

2

) ale n

2

≠ O(nlogn)

15

O – notacja

3. f(n) = n

n ≤ 1 n

2

dla

n ≥ 1

f(n) = O(n

2

)

4.

f(n) = n

2

+5n

n

2

+5n ≤ 2n

2

dla

n ≥ n

0

= 5, stąd c=2 oraz n

0

= 5

n

2

+5n = O(n

2

)

dla c=6 oraz n

0

= 1 zachodzi: n

2

+5n ≤ n

2

+5n

2

= 6 n

2

5.

f(n) = n

2

n

2

= O(n

2

+ 5n)

n

2

≤ 1 (n

2

+5n) dla

c=1 oraz n

0

=0

ASD

LJ

S

O – notacja

7. f(n) = 2n

2

+ 3n + 1 = O(n

2

)

c

≥ 6

≥ 3,8 ≥ 3,2 ≥ 2,9 ≥ 2,7

→ 2

n

0

1

2

3

4

5

→ ∞

Wartości c, n

0

otrzymujemy, rozwiązując nierówność:

2n

2

+ 3n + 1

≤ cn

2

6.

f(n) = 2n

2

+ 15n + 5lg n + 50

f(n) = 2n

2

+ 15n + O(lg n)

f(n) = 2n

2

+ O(n)

f(n) = O(n

2

)

ASD

LJ

S

16

O – notacja

Funkcje T(n) czasowej złożoności określonego algorytmu.

4

2

7

2

11

2

1

)

(

2

3

+

+

+

=

n

n

T

n

n

Dla n > 12 zachodzi:

n

n

n

T

3

3

)

(

2

1

<

<

2

)

1

(

)

(

−

=

n

n

n

T

1.

2

2

)

(

2

)

1

(

2

n

n

n

n

n

=

≤

−

2.

Dla n>0 zachodzi:

T(n)=O(n

2

)

ASD

LJ

S

T(n)=O(n

3

)

O – notacja

n

n

T

n

10

)

(

2

+

=

Dla n

≥ 10 zachodzi:

1.

ASD

LJ

S

n

n

n

n

T

2

2

2

10

)

(

≤

+

=

Możemy przyjąć c=2 oraz n

0

=10, w celu stwierdzenia, że T(n)=O(n

2

).

17

O – notacja

ASD

LJ

S

Dla małych n algorytm2 o większej asymptotycznej złożoności obliczeniowej może
okazać się lepszy. Algorytm lepszy asymptotycznie nie zawsze jest lepszy dla
małych n.

Algorytm1

Algorytm2

Kategorie złożoności

ASD

LJ

S

Określenie werbalne

Określenie formalne

stała

O(1)

liniowa

O(n)

subliniowa

O(n

r

) 0<r<1

logarytmiczna

O(lg n)

liniowo - logarytmiczna

O(n lg n)

kwadratowa

O(n

2

)

subkwadratowa

O(n

r

) 1<r<2

wielomianowa

O(n

k

) k

≥1

wykładnicza

O(r

n

) r>1

Kategorie złożoności (

complexity categories

) są to zbiory funkcji, które mają takie

samo asymptotyczne ograniczenie.

18

Typowe funkcje złożoności

T(n) = O(1): czas realizacji algorytmu jest stały, Większość instrukcji wykonuje

się raz lub kilka razy.

T(n) = O(n): algorytm działa w czasie liniowym (

linear time

), na każdy z n

elementów wejściowych potrzebna jest niewielka ilość czasu przetwarzania.

T(n) = O(lgn): algorytm nieznacznie spowalnia ze wzrostem n. Taka zależność

występuje w przypadkach, kiedy rozwiązywanie polega na transformacji

wyjściowego zadania na szereg cząstkowych zadań, transformacji redukującej

rozmiar zadania wyjściowego (np. przeszukiwanie binarne).

ASD

LJ

S

Typowe funkcje złożoności

T(n) = O(nlgn): Przypadek w którym problem jest rozwiązywany poprzez
rozbicie go na niezależne podproblemy o mniejszym rozmiarze, a następnie
połączenie otrzymanych rozwiązań (np. sortowanie przez scalanie).

T(n) = O(n

k

): Algorytm nadaje się do rozwiązywania relatywnie niedużych

zadań. Przypadek dotyczy z reguły przetwarzania wszystkich par n elementów
wejściowych (np. przetwarzanie dwuwymiarowych tablic).

T(n) = O(2

n

): Algorytmy w niektórych przypadkach są akceptowane w

rozwiązaniach praktycznych. Kiedy n podwaja się czas rośnie do kwadratu (np.
wyznaczanie wszystkich podzbiorów zbioru).

ASD

LJ

S

19

Typowe funkcje złożoności

Wartości najczęściej spotykanych funkcji złożoności.

ASD

LJ

S

n

lg

nlgn

n

2

10

3

33

100

100

7

664

10000

1000

10

9966

1000000

10000

13

132877

100000000

Typowe funkcje złożoności

ASD

LJ

S

Kategorie złożoności (

complexity categories

).

20

Złożoność asymtotyczna

A1 //Ciąg instrukcji
{
s1; s2; ...; sn;
}

O(1)

A2 //Pojedyncza pętla
{

For i=1,2,..., n

s;

}

nO(1) = O(n).

A3 //Podwójna pętla
{
For i:=1,2,...,n

For j:=1,2,...,n

s;

}

O(n

2

)

A4 //Podwójna pętla,zależność indeksów
{

For i:=1,2,..., n
For j:=1,2,..., i

s;

}

)

(

)

2

)

1

(

(

)

(

2

1

n

O

n

n

O

i

O

n

=

+

=

∑

ASD

LJ

S

Własności notacji

Własności „O notacji:

Mnożenie przez stałą:

k f(n) = O(f(n))

k O(f(n)) = O(f(n))

O(k f(n)) = O(f(n))

Suma:

O(f

1

(n))+ ...+ O(f

k

(n)) = O(f

1

(n) + ...+ f

k

(n))

Iloczyn:

O(f(n)) O(g(n)) = O(f(n) g(n))

Przechodniość:

f(n) = O(g(n)) i g(n) = O(h(n))

⇒ f(n) = O((h(n))

ASD

LJ

S

21

Własności notacji

Wielomian wyższego stopnia rośnie szybciej niż wielomian stopnia niższego:

n

r

=O(n

s

)

jeżeli

0

≤ r ≤ s

Funkcja wykładnicza rośnie szybciej niż funkcja wielomianowa:

n

k

=O(b

n

)

dla

b > 1, k

≥ 0

Funkcja logarytmiczna rośnie wolniej niż wielomianowa:

log

b

n =O(n

k

)

dla

b > 1, k > 0

Wszystkie logarytmy rosną w tym samym stopniu:

log

b

n =O(log

d

n) dla

b, d > 1

ASD

LJ

S

Notacje asymtotyczne

Ω

Ω

Ω

Ω - notacja.

Asymptotyczne ograniczenie dolne (

asymptotic lower bound

).

Funkcja f(n) jest co najmniej rzędu g(n) ( f(n)=Ω(g(n)) ) jeżeli:

(

∃ c>0 ) (∃ n

0

≥0 ) ∀ n > n

0

zachodzi: f(n) ≥ c g(n)

f(n) = Ω (g(n)), gdy lim

n

→∞

f(n)/g(n) = +

∞

Inna definicja Ω-notacji:

f(n) = Ω(g(n))

≡ lim

n

→∞

inf

f(n)/g(n)> 0

g(n) = O(f(n)).

ASD

LJ

S

Notacja Ω wymaga istnienia „asymptotycznego ograniczenia dolnego”,

pozwalającego oszacować „od dołu” funkcję f przez funkcję g.

22

Ω

Ω

Ω

Ω - notacja

1. f(n) = 5n

2

5n

2

≥ 1

⋅ n

2

dla c = 1, n

0

= 0, n ≥ n

0

f(n) = Ω(n

2

)

2

)

1

(

)

(

−

=

n

n

n

f

Dla n ≥ 2 zachodzi (n-1) ≥ n/2

4

2

2

2

)

1

(

)

(

2

n

n

n

n

n

n

f

=

⋅

≥

−

=

c = 1/4, n

0

= 2

f(n) = Ω(n

2

).

2.

2

2

)

(

2

)

1

(

)

(

2

n

n

n

n

n

n

f

=

≤

−

=

c = 1/2, n

0

= 0

f(n) = O(n

2

).

ASD

LJ

S

Θ

Θ

Θ

Θ - notacja

Θ

- notacja.

Funkcja f(n) jest rzędu Θ(g(n)) ( f(n)=Θ(g(n) ) ) jeżeli:

(

∃ c

1

, c

2

>0 ) (

∃ n

0

≥0 ) ∀ n ≥ n

0

zachodzi: c

1

g(n)

≤f(n)≤c

2

g(n)

f(n) = Θ(g(n)), gdy lim

n

→∞

f(n)/g(n) = const

Θ(g(n)) = O(g(n))

∩ Ω(g(n))

Ω( )

O( )

Θ( )

ASD

LJ

S

Sens notacji Θ polega na istnieniu „asymptotycznego ograniczenia dolnego i górnego”,
pozwalającego oszacować „od dołu” i „od góry” funkcję f przez funkcję g.

23

Θ

Θ

Θ

Θ - notacja

4

2

7

2

11

2

1

)

(

2

3

+

+

+

=

n

n

n

n

T

3

3

)

(

2

1

n

n

T

n

<

<

Dla c

1

= 1/2, c

2

= 1 oraz n

0

= 12

T(n)= O(n

3

)

∩ Ω(n

3

)= Θ(n

3

)

Dla c

1

= 1/4, c

2

= 1/2 oraz n

0

= 2

2

)

1

(

)

(

−

=

n

n

n

T

2

2

2

1

)

(

4

1

n

n

T

n

<

<

T(n)= O(n

2

)

∩ Ω(n

2

)= Θ(n

2

)

Ω

O

2n

2

3n

2

+6

5n

2

+2n

5n+7
2nlgn

2n

2

3n

2

+6

5n

2

+2n

2

n

+4n

4n

3

+3n

2

O(n

2

)

Ω

(n

2

)

O( )

5n+7
2nlgn

Ω( )

Θ

( )

2n

2

3n

2

+6

5n

2

+2n

2

n

+4n

4n

3

+3n

2

Θ

(n

2

)= O(n

2

)∩

Ω

(n

2

)

ASD

LJ

S

Złożoność obliczeniowa

Nierealizowalność algorytmu jest wewnętrzną cechą algorytmów o złożoności

wykładniczej.

ASD

LJ

S

Rozmiar danych n

30

50

60

Liczba operacji 2

n

0.1 10

10

10

15

10

18

Czas działania
(10

-10

s/op.)

0.1 s

10

5

s

(28h)

10

8

s

(3 lata)

Czas działania

(10

-13

s/op.)

0.1 10

-3

s

10

2

s

10

5

s

(28h)

Charakteryzowanie w sposób asymptotyczny efektywności algorytmu jest abstrakcją,
w której pomija się szczegóły. Posługiwanie się tą miarą wymaga uświadomienia
sobie szczegółów, które taka abstrakcja ukrywa.

24

Rodzaje złożoności obliczeniowej

Złożoność pesymistyczna (

worst-case complexity

),

Złożoność oczekiwana (

average-case complexity

),

Złożoność optymistyczna (

best-case complexity

).

ASD

LJ

S

Rodzaje złożoności obliczeniowej

Oznaczenia.

D

n

- zbiór możliwych zestawów danych (instancji) o rozmiarze n

I - zestaw danych, element zbioru D

n

(I

∈ D

n

)

t(I) - liczba operacji podstawowych dla zestawu danych wejściowych I

∈D

n

X

n

- zmienna losowa, której wartością jest t(I) dla I

∈D

n

p

n,k

– prawdopodobieństwo tego, że dla zestawu danych I wykonano k

operacji dominujących, p

n,k

=P

n

(X

n

=k)

P

n

- rozkład prawdopodobieństwa ( z reguły równomierny) zmiennej losowej X

n

.

ASD

LJ

S

25

Rodzaje złożoności obliczeniowej

Złożoność pesymistyczna

(worst case running time)

T

worst

(n) = sup { t(I): I

∈D

n

}

Złożoność oczekiwana

(average case running time) (wartość oczekiwana

zmiennej losowej X

n

)

Złożoność optymistyczna

(worst case running time)

T

best

(n) = inf { t(I): I

∈D

n

}

T

ave

(n) = E(X

n

) =

Σ

k

≥0

k p

n,k

ASD

LJ

S

Wrażliwość obliczeniowa algorytmu

Wrażliwość pesymistyczna

(worst- case sensitivity):

∆

wcs

(n) = T

worst

(n) – T

best

(n) = sup { t(I

1

) - t(I

2

): I

1

, I

2

∈D

n

}

Wrażliwość oczekiwana

(average- case sensitivity):

δ

acs

(n) = dev(Xn) =

√ Var(Xn)

gdzie: dev(X

n

) – standardowe odchylenie zmiennej losowej X

n

,

var(X

n

) – wariancja zmiennej losowej X

n

,

p

k

k

n,

2

k≥0

n

)

(

X

n

)

(

(

)

X

var(

−

=

∑

E

ASD

LJ

S