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
1
Analiza algorytmów
Aspekty analizy algorytmów:
Poprawności semantycznej algorytmu.
Złożoności obliczeniowej: czasowej, pamięciowej.
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.
Analiza algorytmów uwzględnia: poprawność semantyczną, czas działania, zajętość
pamięci, optymalność, okoliczności użycia algorytmu.
ASD LJ S
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
2
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
3
Złożoność obliczeniowa algorytmów
Computational Complexity
Hartmanis J., Stearns R. On the Computational
Complexity of Algorithms , 1965)
Złożoność obliczeniowa
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.
ASD LJ S
4
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.
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.
ASD LJ S
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ęzle, przejście po krawędzi (algorytmy grafowe).
Przykłady operacji, które nie są elementarnymi to instrukcje: WHILE, REPEAT, FOR.
ASD LJ S
5
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).
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).
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.
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.
ASD LJ S
Rozmiar danych wejściowych
Rozmiar danych wejściowych (przykłady).
1. W problemie sortowania ciągu skończonego a1 a2, ... , an 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ą.
ASD LJ S
6
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.
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(xd"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
ASD LJ S
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.
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
}
ASD LJ S
7
Złożoność obliczeniowa
Liczba operacji elementarnych w algorytmie Max pciag V1 zależy od:
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:
j
n n n n n
(n-i +1)(n-i +2) 1 1 1
K(n) = = n3 + n2 + n
" " "1=" "( j -i +1) ="
2 6 2 3
i=1 j=i k=i i=1 j=i i=1
Liczba wykonań instrukcji w pętli po j:
n n n
J(n) = = - i +1) = = n2 + n
" "1 "(n n(n +1) 1 1
2 2 2
i=1 j=i i=1
Złożoność pesymistyczna:
1 17
T(n) =3+5J(n)+ K(n)+1= n3 +3n2 + n +4
6 6
ASD LJ S
Złożoność obliczeniowa
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
}
ASD LJ S
8
Złożoność obliczeniowa
Liczba wykonań instrukcji w pętli wewnętrznej:
n n n
n(n + 1) 1 1
2
J (n) = = i = = n + n
" "1 "
2 2 2
i =1 j =i i=1
J(n) liczba obrotów pętli po j.
I(n) liczba obrotów pętli po i.
I(n) = n
Złożoność pesymistyczna:
5 7
2
T (n) = 3 + I (n) + 5J (n) + 1 = n + n + 4
2 2
ASD LJ S
Złożoność obliczeniowa
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
J(n) liczba obrotów
i=1; 1
pętli po j.
asum=0; 1
FOR(j=1,2,& ,n){ n
asum=asum+A[j]; J(n)
J(n) = n
IF (asum>maxsum){ J(n)
maxsum=asum; J(n)
T(n) =8n+6
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
}
ASD LJ S
9
Złożoność obliczeniowa
Porownanie czasów wykonania algorytmów
Złożoność czasowa (liczba elementarnych operacji)
Rozmiar Algorytm Algorytm Algorytm
problemu n Max pciag V1 Max pciag V2 Max pciag V3
10 500 300 100
102 200 103 25 103 103
103 2 108 2.5 106 8 103
104 1.5 1011 2.5 108 8 104
105 1.5 1014 2.5 109 8 105
ASD LJ S
Złożoność obliczeniowa
Porownanie czasów wykonania algorytmów
Złożoność czasowa (w jednostkach czasowych)
Rozmiar problemu Algorytm Algorytm Algorytm
n Max pciag V1 Max pciag V2 Max pciag V3
10 0.5 ms 0.3 ms 0.1 ms
102 0.2 s 25 ms 1 ms
103 200 s 2.5 s 8 ms
104 45 godz. 5 min 0.8 ms
105 4.5 lat 50 min 0.8 s
Założony czas wykonywania elementarnej operacji wynosi 10-6 s.
Konwersja sekund
102 s 2 min 106 s 1,5 tyg. 109 s 30 lat
104 s 3 godz. 108 s 3 lata 1010 s 300 lat
ASD LJ S
10
Złożoność obliczeniowa
Porownanie czasów wykonania algorytmów
Złożoność czasowa (liczba elementarnych operacji)
Rozmiar problemu Algorytm Algorytm Algorytm
n Max pciag V1 Max pciag V2 Max pciag V3
10 0.5 s 0.3 s 0.1 s
102 0.2 ms 0.025 ms 0.001 ms
103 0.2 s 2.5 ms 0.008 ms
104 3 min 0.25 s 0.08 ms
105 45 godz 2.5 s 0.8 ms
Założony czas wykonywania elementarnej operacji wynosi 10-9 s.
ASD LJ S
Złożoność obliczeniowa
Porownanie czasów wykonania algorytmów
Złożoność czasowa (liczba elementarnych operacji)
Rozmiar Algorytm Algorytm Algorytm
problemu n Max pciag V1 Max pciag V2 Max pciag V3
10 0.5 ns 0.3 ns 0.1 ns
102 0.2 s 25 ns 1 ns
103 0.2 m s 2.5 s 8 ns
104 0.15 s 0.25 ms 80 ns
105 3 min 2.5 ms 0.8 s
Założony czas wykonywania elementarnej operacji wynosi 10-12 s.
ASD LJ S
11
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).
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ęzle, krawędzi
ASD LJ S
12
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 ) (" n0 e" 0 ) " n e" n0 zachodzi f(n)d" c g(n).
f(n) =O(g(n)) gdy lim f(n)/g(n) = 0.
n "
g(n) `" O(f(n)).
Inna definicja O-notacji:
f(n) =O(g(n)) a" lim n " sup ćłf(n)/g(n) ćł< "
Paul Bachman (1892)
ASD LJ S
13
Notacje asymtotyczne
Symbol O(g(n)) oznacza zbiór funkcji f: NR+ zdefiniowany następująco:
O( g(n) ) = {f" R+: istnieje taka stała c>0 i n0"N, że f(n)d"c g(n) dla
każdego n > n0 }
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) = n2/2 = O(n3)
n2 / 2 = 1 = 0
lim lim
n " n "
2n
n3
2. f(n) = nlogn = O(n2)
logba = logca / logcb
nlogn lnn 1/ n
= = = 0
lim lim lim
n " n " n "
nln2 ln2
n2
Wniosek:
nlogn = O(n2) ale n2 `" O(nlogn)
ASD LJ S
14
O notacja
3. f(n) = n
n d" 1 n2 dla n e" 1
f(n) = O(n2)
4. f(n) = n2+5n
n2+5n d" 2n2 dla n e" n0= 5, stąd c=2 oraz n0 = 5
n2+5n = O(n2)
dla c=6 oraz n0 = 1 zachodzi: n2+5n d" n2+5n2 = 6 n2
5. f(n) = n2
n2 = O(n2 + 5n)
n2 d" 1 (n2+5n) dla c=1 oraz n0=0
ASD LJ S
O notacja
6. f(n) = 2n2 + 15n + 5lg n + 50
f(n) = 2n2 + 15n + O(lg n)
f(n) = 2n2 + O(n)
f(n) = O(n2)
7. f(n) = 2n2 + 3n + 1 = O(n2)
Wartości c, n0 otrzymujemy, rozwiązując nierówność:
2n2 + 3n + 1 d" cn2
c e" 6 e" 3,8 e" 3,2 e" 2,9 e" 2,7 2
n0 1 2 3 4 5 "
ASD LJ S
15
O notacja
Funkcje T(n) czasowej złożoności określonego algorytmu.
1 11 7
3 2
1. T(n) = + + n + 4
n n
2 2 2
Dla n > 12 zachodzi:
1
3 3
< T (n) <
n n
2
T(n)=O(n3)
n(n-1)
2.
T(n) =
2
Dla n>0 zachodzi:
2
n ( n - 1) n (n )
n
d" =
2 2 2
T(n)=O(n2)
ASD LJ S
O notacja
2
1. T (n) = + 10 n
n
Dla n e" 10 zachodzi:
2 2
T (n) = + 10n d" 2
n n
Możemy przyjąć c=2 oraz n0=10, w celu stwierdzenia, że T(n)=O(n2).
ASD LJ S
16
O notacja
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.
Algorytm2
Algorytm1
ASD LJ S
Kategorie złożoności
Kategorie złożoności (complexity categories) są to zbiory funkcji, które mają takie
samo asymptotyczne ograniczenie.
Określenie formalne Określenie werbalne
O(1) stała
O(n) liniowa
O(nr) 0
O(lg n) logarytmiczna
O(n lg n) liniowo - logarytmiczna
O(n2) kwadratowa
O(nr) 1O(nk) ke"1 wielomianowa
O(rn) r>1 wykładnicza
ASD LJ S
17
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(nk): 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(2n): 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
18
Typowe funkcje złożoności
Wartości najczęściej spotykanych funkcji złożoności.
n lg nlgn n2
10 3 33 100
100 7 664 10000
1000 10 9966 1000000
10000 13 132877 100000000
ASD LJ S
Typowe funkcje złożoności
Kategorie złożoności (complexity categories).
ASD LJ S
19
Złożoność asymtotyczna
A1 //Ciąg instrukcji A2 //Pojedyncza pętla
{ {
s1; s2; ...; sn; For i=1,2,..., n
} s;
}
O(1)
nO(1) = O(n).
A3 //Podwójna pętla
A4 //Podwójna pętla,zale\ność indeksów
{
{
For i:=1,2,...,n
For i:=1,2,..., n
For j:=1,2,...,n
For j:=1,2,..., i
s;
s;
}
}
n
n(n +1) 2
O( = O( ) = O( )
"i) 2 n
1
O(n2)
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(f1(n))+ ...+ O(fk(n)) = O(f1(n) + ...+ fk(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
20
Własności notacji
Wielomian wyższego stopnia rośnie szybciej niż wielomian stopnia niższego:
nr =O(ns) jeżeli 0 d" r d" s
Funkcja wykładnicza rośnie szybciej niż funkcja wielomianowa:
nk =O(bn) dla b > 1, k e" 0
Funkcja logarytmiczna rośnie wolniej niż wielomianowa:
logbn =O(nk) dla b > 1, k > 0
Wszystkie logarytmy rosną w tym samym stopniu:
logbn =O(logdn) dla b, d > 1
ASD LJ S
Notacje asymtotyczne
Asymptotyczne ograniczenie dolne (asymptotic lower bound).
&! - notacja.
&!
&!
&!
Funkcja f(n) jest co najmniej rzędu g(n) ( f(n)=&!(g(n)) ) jeżeli:
(" c>0 ) (" n0 e"0 ) " n > n0 zachodzi: f(n) e" c g(n)
f(n) = &! (g(n)), gdy lim f(n)/g(n) = + "
n "
Inna definicja &!-notacji:
f(n) = &!(g(n)) a" lim n " inf ćłf(n)/g(n)ćł> 0
g(n) = O(f(n)).
Notacja &! wymaga istnienia asymptotycznego ograniczenia dolnego ,
pozwalającego oszacować od dołu funkcję f przez funkcję g.
ASD LJ S
21
&! - notacja
&!
&!
&!
1. f(n) = 5n2
5n2 e" 1" n2 dla c = 1, n0 = 0, n e" n0
f(n) = &!(n2)
n(n -1)
f (n) =
2.
2
Dla n ? 2 zachodzi (n-1) ? n/2
2
n (n - 1) n n
n
f (n ) = e" " = n(n -1) n(n)
n2
f (n) = d" =
2 2 2 4
2 2 2
c = 1/4, n0 = 2
c = 1/2, n0 = 0
f(n) = &!(n2).
f(n) = O(n2).
ASD LJ S
Ś - notacja
Ś
Ś
Ś
Ś - notacja.
Funkcja f(n) jest rzędu Ś(g(n)) ( f(n)=Ś(g(n) ) ) jeżeli:
(" c1, c2>0 ) (" n0 e"0 ) " n e" n0 zachodzi: c1g(n)d"f(n)d"c2 g(n)
f(n) = Ś(g(n)), gdy lim f(n)/g(n) = const
n "
Ś(g(n)) = O(g(n)) )" &!(g(n))
O( )
Ś( )
&!( )
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.
ASD LJ S
22
Ś - notacja
Ś
Ś
Ś
1 11 7
n(n -1)
T(n) = n3 + n2 + n + 4
T (n) =
2 2 2
2
Dla c1 = 1/2, c2 = 1 oraz n0 = 12
Dla c1 = 1/4, c2 = 1/2 oraz n0 = 2
1 1 1
3 3
n2 < T(n) < n2 n < T (n) < n
4 2 2
T(n)= O(n3) )" &!(n3)= Ś(n3)
T(n)= O(n2) )" &!(n2)= Ś(n2)
O &! O( ) &!( )
Ś( )
2n2 2n2
3n2+6 3n2+6
5n+7
2n2 2n+4n
5n2+2n 5n2+2n
4n3+3n2
2nlgn
3n2+6
5n+7 2n+4n
5n2+2n
2nlgn 4n3+3n2
O(n2)
&!(n2) Ś(n2)= O(n2))"&!(n2)
ASD LJ S
Złożoność obliczeniowa
Nierealizowalność algorytmu jest wewnętrzną cechą algorytmów o złożoności
wykładniczej.
Rozmiar danych n 30 50 60
Liczba operacji 2n 0.1 1010 1015 1018
Czas działania 0.1 s 105 s 108 s
(10-10 s/op.) (28h) (3 lata)
Czas działania 0.1 10-3 s 102 s 105 s
(10-13 s/op.) (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.
ASD LJ S
23
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.
Dn - zbiór możliwych zestawów danych (instancji) o rozmiarze n
I - zestaw danych, element zbioru Dn (I " Dn)
t(I) - liczba operacji dominujących dla zestawu danych wejściowych I"Dn
Xn - zmienna losowa, której wartością jest t(I) dla I"Dn
pn,k prawdopodobieństwo tego, że dla zestawu danych I wykonano k
operacji dominujących, pn,k=Pn(Xn=k)
Pn - rozkład prawdopodobieństwa ( z reguły równomierny) zmiennej losowej Xn.
ASD LJ S
24
Rodzaje złożoności obliczeniowej
Złożoność pesymistyczna (worst case running time)
Tworst(n) = sup { t(I): I"Dn}
Złożoność oczekiwana (average case running time) (wartość oczekiwana
zmiennej losowej Xn)
Tave(n) = E(Xn) = k pn,k
Ł
ke"0
Złożoność optymistyczna (worst case running time)
Tbest(n) = inf { t(I): I"Dn }
ASD LJ S
Wrażliwość obliczeniowa algorytmu
Wrażliwość pesymistyczna (worst- case sensitivity):
" (n) = Tworst(n) Tbest(n) = sup { t(I1) - t(I2): I1, I2"Dn }
wcs
Wrażliwość oczekiwana (average- case sensitivity):
acs(n) = dev(Xn) = " Var(Xn)
gdzie: dev(Xn) standardowe odchylenie zmiennej losowej Xn,
var(Xn) wariancja zmiennej losowej Xn,
= (Xn)
)2 pn,k
var( ) ((k - E
Xn
"
ke"0
ASD LJ S
25
Złożoność obliczeniowa
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.
Search (A,n,x)
//A-tablica indeksowana od 1 do n+1
{
A[n+1]=x;
1. ind=1;
2. WHILE (indd"n and A[ind]`"x){
3. ind=ind+1;
}
4. IF (ind>n) {
5. ind=0;
}
6. return(ind)
}
ASD LJ S
Złożoność obliczeniowa
Analiza najgorszego przypadku:
- x zajmuje ostatnią pozycję Tworst(n) = n,
- x nie występuje w tablicy Tworst(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.
1
dla i = 1,2,..,n
pn,i =
n
n n n
1 1
1 n(n+1) = (n+1)
pn,i t (Ii) =
Ł Ł i = Ł i =
Tave(n) =
n
n n 2 2
i=1 i=1 i=1
ASD LJ S
26
Złożoność obliczeniowa
Przypadek kiedy x może nie znajdować się w tablicy:
Ii zestaw danych dla przypadku, gdy x jest na i-tej pozycji,
In+1 zestaw danych, gdy przypadku, gdy x nie ma w tablicy,
q - oznacza prawdopodobieństwo tego, że x jest w tablicy,
Dla 1 d" i d" n: pn,i=q/n, t(Ii)=i
pn+1,n=1-q, t(In+1)=n+1
n+1 n
q
n(n+1)
Tave(n) = pn,i t (Ii) =
Ł Ł i +(1 q) (n+1)= q
+ (1- q)(n+1)
n
i=1 i=1 2n
Dla q=1: Tave(n) = (n+1)/2,
Dla q=1/2: Tave(n) = (n+1)/4 +(n+1)/2
ASD LJ S
Wrażliwość algorytmu
Przeszukiwanie liniowe tablicy.
1. Wrażliwość pesymistyczna:
"wcs(n) = Tworst(n) Tbest(n) = O(n)-O(1)= O(n)
2. Wrażliwość oczekiwana:
n n
2 2
n +1 1 1 n +1
Var(X n) = - ) "(i =
(t(Ii) = - )
"
2 n n 2
i=1 i
1 n(n +1)(2n +1) 2(n +1)n(n +1) n(n +1)2 (n +1)(2n +1) (n +1)2
= ( - + ) = - =
n 6 4 4 6 4
2
-1
n +1 1 2
n
= (4n + 2 - 3n - 3) = H"
n
12 12 12
(n) H" "(n2/12) H" 0.29 n
ASD LJ S
27
Złożoność obliczeniowa
Złożoność obliczeniowa w każdym przypadku (every-case time complexity).
SORT(n)
MULT(n)
// n rozmiar danych we.
//n rozmiar danych we.
}
{
For i=1,2,...,n-1 {
For j=i+1, ...,n { FOR i=1,2,...,n
Operacja podstawowa
FOR j=1,2,...,n
}
FOR k:=1,2,...,n{
}
Operacja dominująca
}
}
}
Tave(n) = Tbest(n) = (n-1) + (n-2) + ...+1
= (n (n-1)) = (n2 n)
Tave(n) = Tbest(n) = n3
Tec(n) = (n-1)n/2 selection_sort.
Tec(n) = n3 mnożenie tablic
dwuwymiarowych,
ASD LJ S
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] d" A[2] d" ... d" A[n]).
- Liczba o wartości x.
Dane wyjściowe:
Liczba całkowita ind, taka że albo 1d" ind d" n, wtedy A[ind]=x, albo ind=0 wówczas
elementu równego x nie ma w tablicy (" j takiego że p d" j d" k, A[j]`"x oznacza brak
elementu x w tablicy).
ASD LJ S
28
Wyszukiwanie binarne
Search binary (A,p,k,x)
{
lewy=p;
prawy=k;
ind=0;
WHILE (lewyd"prawy and ind=0){
q=ł(prawy+lewy)/2ł;
IF (x=A[q]) ind=q;
IF (xELSE (x>A[q])lewy=q+1;
Wywołanie procedury:
}
Binary_search (A,1,n,x)
}
Załóżmy n = 25
A[16] A[24] A[28] A[30] A[31 ] A[32]
Liczba obrotów iteracji:
A[16]A[24]A[28]A[30]A[31]A[32] A[32]
lgn+1=lg32+1=6
4 55 6
1 1 2 2 33 4 6
ASD LJ S
Wyszukiwanie binarne
Załóżmy n = 26
A[1] A[32] A[64]
A[16]A[24]A[28]A[30]A[31]A[32] A[32]
4 5 6
1 2 3 1
Liczba obrotów iteracji:
lg n+1=lg64 +1=7
A[16] A[24] A[28] A[30] A[31 ] A[32]
A[16]A[24]A[28]A[30]A[31]A[32] A[32]
4 55 6
3
1 1 2 2 3 4 6
ASD LJ S
29
Wyszukiwanie binarne
n=2k
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 2k < n < 2k+1 zachodzi T(2k) < T(n) < T(2k+1)
ASD LJ S
Wyszukiwanie liniowe
Search lin (A,n,x)
{
A[n+1]=x
ind=1;
WHILE(indd"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
30
Złożoność pamięciowa
Space complexity
Złożoność pamięciowa
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.
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 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ą.
Dane istotne (essential data) dane, które nie mogą być pominięte w trakcie działania
algorytmu.
ASD LJ S
31
Złożoność pamięciowa
Jeśli pamięć jest stała względem rozmiaru danych n, to algorytm działa w miejscu (in
place, in situ).
Max pciag(A,n,start,fin)
{
...
Złożoność pamięciowa algorytmu jest stała O(1).
& .
FOR (j:=1,2,& ,n){
input(x);
act_sum=act_sum+x;
& &
& &
}
& &
}
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
32
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
33
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.
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]
B[i,j] C[min(i,j), max(i,j)]
A[2,1] 0 B[2,3]
C=
A[3,1] A[3,2] 0
A[i,j] C[max(i,j), min(i,j)]
ASD LJ S
34
Wyszukiwarka
Podobne podstrony:
nw asd w2
nw asd w3
nw asd w9
nw asd w1
nw asd w6
nw asd w7
nw asd w8
nw asd w5
nw asd w10
nw asd w11
nw asd w4
więcej podobnych podstron