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)]