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

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.

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

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 dominujących 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

26

Złożoność obliczeniowa

Search (A,n,x)
//A-tablica indeksowana od 1 do n+1
{

A[n+1]=x;

1.

ind=1;

2.

WHILE (ind≤n and A[ind]≠x){

3.

ind=ind+1;

}

4.

IF (ind>n) {

5.

ind=0;

}

6.

return(ind)

}

Przykład.

Przeszukiwanie liniowe (n+1)-elementowej tablicy A ze względu na pierwsze
wystąpienie elementu o wartości x. Poszukiwane elementy znajdują się na miejscach
A[1], A[2], …, A[n].

Operacja dominująca: porównywanie elementów tablicy z wartością x.

ASD

LJ

S

Złożoność obliczeniowa

Analiza najgorszego przypadku:

- x zajmuje ostatnią pozycję T

worst

(n) = n,

- x nie występuje w tablicy

T

worst

(n) = n+1.

Analiza średniego przypadku:

Założenia:
-

wszystkie elementy tablicy są różne,

-

x należy do tablicy A,

-

x może być na każdej pozycji z jednakowym prawdopodobieństwem.

T

ave

(n)

=

p

n,i

t (I

i

) =

Σ

i=1

n

n

1

i =

n

1

i =

n

1

2

n(n+1) =

2

(n+1)

Σ

i=1

n

Σ

i=1

n

ASD

LJ

S

n

1

p

n,i

=

dla i = 1,2,..,n

27

Złożoność obliczeniowa

Przypadek kiedy x może nie znajdować się w tablicy:

I

i

– zestaw danych dla przypadku, gdy x jest na i-tej pozycji,

I

n+1

– zestaw danych, gdy przypadku, gdy x nie ma w tablicy,

q - oznacza prawdopodobieństwo tego, że x jest w tablicy,

Dla 1

≤ i ≤ n: p

n,i

=q/n,

t(I

i

)=i

p

n+1,n

=1-q,

t(I

n+1

)=n+1

T

ave

(n)

=

p

n,i

t (I

i

) =

Σ

i=1

n+1

n

q

i +(1 –q) (n+1)= q

2n

n(n+1)

Σ

i=1

n

+ (1- q)(n+1)

Dla q=1:

T

ave

(n) = (n+1)/2,

Dla q=1/2:

T

ave

(n) = (n+1)/4 +(n+1)/2

ASD

LJ

S

Wrażliwość algorytmu

Przeszukiwanie liniowe tablicy.

1.

Wrażliwość pesymistyczna:

∆

wcs

(n) = T

worst

(n) – T

best

(n) = O(n)-O(1)= O(n)

2.

Wrażliwość oczekiwana:

n

n

n

n

n

n

n

n

n

n

n

n

n

n

n

n

n

n

i

n

n

n

I

t

X

Var

n

i

n

i

i

n

2

2

2

2

2

2

1

12

1

12

1

)

3

3

2

4

(

12

1

4

)

1

(

6

)

1

2

)(

1

(

)

4

)

1

(

4

)

1

(

)

1

(

2

6

)

1

2

)(

1

(

(

1

2

1

1

1

2

1

)

(

)

(

)

(

)

(

≈

−

=

−

−

+

+

=

=

+

−

+

+

=

+

+

+

+

−

+

+

=

=

+

−

=

+

−

=

∑

∑

=

δ(n) ≈ √(n

2

/12)

≈ 0.29 n

ASD

LJ

S

28

Złożoność obliczeniowa

Złożoność obliczeniowa w każdym przypadku (

every-case time complexity

).

SORT(n)
// n–rozmiar danych we.
}

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

For j=i+1, ...,n {

Operacja podstawowa

}

}

}

T

ave

(n) = T

best

(n) = (n-1) + (n-2) + ...+1

= ½ (n (n-1)) = ½ (n

2

– n)

T

ec

(n) = (n-1)n/2

→ selection_sort.

ASD

LJ

S

MULT(n)

//n–rozmiar danych we.

{

FOR i=1,2,...,n

FOR j=1,2,...,n

FOR k:=1,2,...,n{

Operacja dominująca

}

}

T

ave

(n) = T

best

(n) = n

3

T

ec

(n) = n

3

→ mnożenie tablic

dwuwymiarowych,

Złożoność obliczeniowa

Wyszukiwanie binarne (iteracyjne).

Sformułowanie zadania: Czy x znajduje się w uporządkowanej n-elementowej

tablicy A?.

Dane wejściowe:

-

Tablica uporządkowana A liczb, (A[1]

≤ A[2] ≤ ... ≤ A[n]).

-

Liczba o wartości x.

Dane wyjściowe:

Liczba całkowita ind, taka że albo 1

≤ ind ≤ n, wtedy A[ind]=x, albo ind=0 wówczas

elementu równego x nie ma w tablicy (

∀ j takiego że p ≤ j ≤ k, A[j]≠x oznacza brak

elementu x w tablicy).

ASD

LJ

S

29

Wyszukiwanie binarne

Search binary (A,p,k,x)
{

lewy=p;
prawy=k;
ind=0;
WHILE (lewy≤prawy and ind=0){

q=(prawy+lewy)/2;
IF (x=A[q]) ind=q;
IF (x<A[q]) prawy=q-1

ELSE (x>A[q])lewy=q+1;

}

}

Załóżmy n = 2

5

A[16]A[24]A[28]A[30]A[31]A[32] A[32]

1

2

3

4

5

6

A[16]

A[24]

A[28] A[30] A[31 ] A[32]

1

2

3

4

5

6

Wywołanie procedury:

Binary_search (A,1,n,x)

Liczba obrotów iteracji:

lgn+1=lg32+1=6

ASD

LJ

S

Wyszukiwanie binarne

Załóżmy n = 2

6

A[16]A[24]A[28]A[30]A[31]A[32] A[32]

1

2

3

4

5

6

A[1]

A[32]

A[64]

1

A[16]A[24]A[28]A[30]A[31]A[32] A[32]

1

2

3

4

5

6

A[16]

A[24]

A[28] A[30] A[31 ] A[32]

1

2

3

4

5

6

Liczba obrotów iteracji:

lg n+1=lg64 +1=7

ASD

LJ

S

30

Wyszukiwanie binarne

n=2

k

T(1) = 1
T(2) = 2
T(4) = 3

...............

T(32) = 6

T(n) = log n+1

1.

T(1)= 1

2.

Założenie:

T(n) = logn + 1

Teza:

T(2n) = log(2n) + 1

Dw.

⇒

⇒

⇒

⇒

T(2n) = T(n) + 1 = (log n + 1) + 1 = (log n + lg 2) + 1 = log 2n + 1;

⇐

⇐

⇐

⇐ T(2n) = log 2n + 1 = (log n + 1) + 1 = T(n) + 1;

T(n) = O(log n)

Dla 2

k

< n < 2

k+1

zachodzi T(2

k

) < T(n) < T(2

k+1

)

ASD

LJ

S

Wyszukiwanie liniowe

Search lin (A,n,x)
{

A[n+1]=x

ind=1;

WHILE(ind≤n ∧ A[ind]≠x){

ind=ind+1;

}
IF (ind>n)

ind=0;

return(ind);

}

Złożonośc czasowa algorytmu : Search lin: T(n) = T(n)=n O(1)= O(n) O(1)=O(n).

Rozm. tab. Wyszuk. liniowe Wyszuk. binar.

128 128 8
1024 1024 11
1048576 1048576 21

4 294 967 296 4 294 967 296 31

ASD

LJ

S

31

Złożoność pamięciowa

Space complexity

Złożoność pamięciowa

Rodzaje złożoności pamięciowej:



Złożoność pamięciowa oczekiwana (expected space complexity),



Złożoność pamięciowa najgorszego przypadku (worst-case space complexity).

Złożoność pamięciowa – wielkość obszaru pamięci (liczba komórek pamięci)
używanych przez program implementujący algorytm. Jednostki: B, kB, MB, GB, TB.

Dane istotne (

essential data

) – dane, które nie mogą być pominięte w trakcie działania

algorytmu.

ASD

LJ

S

Złożoność pamięciowa podobnie jak w przypadku złożoności czasowej jest określana
jako funkcja rozmiaru danych n. Funkcja ta określa ilość zajętej pamięci podczas
działania algorytmu, przy założeniu, że na każdą zmienną elementarną potrzebna jest
jedna komórka pamięci. Zwykle ilość pamięci nie zależy od wartości danych, a tylko
od ich rozmiaru. Dlatego też za złożoność pamięciową przyjmuje się złożoność
pesymistyczną.

32

Złożoność pamięciowa

Max pciag(A,n,start,fin)
{

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

input(x);
act_sum=act_sum+x;

……

……

}
……

}

Złożoność pamięciowa algorytmu jest stała

O(1).

Jeśli pamięć jest stała względem rozmiaru danych n, to algorytm działa w miejscu (in
place, in situ).

ASD

LJ

S

Złożoność pamięciowa

Metody obniżania złożoności pamięciowej.

Wielokrotne obliczanie wartości,

Implementacja struktur rozproszonych,

Kompresja danych,

Strategie przydziału pamięci.

ASD

LJ

S

33

Wielokrotne obliczanie wartości

Pamięć potrzebna do przechowywania danego obiektu może zmniejszyć się, jeśli
nie zapamiętamy go, a zamiast tego będziemy obliczać jego wartość za każdym
razem, gdy będzie ona potrzebna.
Dla przykładu tablicę liczb pierwszych można zastąpić procedurą sprawdzającą,
czy jakaś liczba naturalna jest liczbą pierwszą.
Zamiast pamiętać cały obiekt, przechowujemy jedynie program, który go generuje
i wartość startową (generator), określającą ten konkretny obiekt.

ASD

LJ

S

Stosowanie struktur rozproszonych

Różnorodne tablice, macierze rzadkie (

sprase

matrix

), grafy używane w

programach są często strukturami rozproszonymi. Do ich implementacji można
używać specjalnych struktur listowych o złożoności pamięciowej O(n), gdzie n jest
liczbą elementów niezerowych.

ASD

LJ

S

34

Kompresja danych

Koncepcje umożliwiające ograniczenie pamięci przez stosowanie kompresji
danych pochodzą z teorii informacji.
Jeżeli np. elementy macierzy rzadkiej przyjmują tylko dwie wartości, to możemy
zapamiętać je w postaci upakowanej na bitach.
Podobnie dwie cyfry dziesiętne a i b można zapisać w jednym bajcie za pomocą
liczby n=10a+b.
Do odkodowania informacji służą wówczas dwie instrukcje:

a = n

div

10

b = n

mod

10

ASD

LJ

S

Strategie przydziału pamięci

Czasami ilość dostępnej pamięci nie jest tak ważna jak sposób jej wykorzystania.
Do optymalizacji przydziału pamięci stosuje się techniki: dynamiczny przydział
pamięci, rekordy zmiennej długości, odzyskiwanie pamięci, dzielenie pamięci.

ASD

LJ

S

Jeżeli dane są dwie macierze symetryczne A i B o rozmiarach nxn, przy czym obie
mają zera na głównej przekątnej, to można przechowywać tylko macierz trójkątną
każdej z nich.
Można zatem pozwolić, aby obie tablice dzieliły przestrzeń macierz kwadratowej
C, której jeden z narożnych fragmentów mialby postać:

0

B[1,2]

B[1,3]

A[3,1]

A[3,2]

0

A[2,1]

0

B[2,3]

C=

A[i,j]

→ C[max(i,j), min(i,j)]

B[i,j]

→ C[min(i,j), max(i,j)]