Obsah přednášky ► Analýza
algoritmu
► Algoritmická ► Návrhy
složitost
algoritmů
► Urychlování
algoritmů
1/41
Analýza algoritmu ► Proč
vůbec dělat analýzu?
►
pro většinu problémů existuje několik různých přístupů
►
aby bylo možné vybrat ten správný, potřebujeme umět algoritmy porovnat
2/41
Analýza algoritmu ► Příklad
(dvě řazení pole)
Sort1(a,n) { for(i=1; i
=1)&&(a[j]>t)) { a[j+1]=a[j]; j=j-1; } a[j+1]=t; } }
Sort2(a,p,r) { if(r>p) { q = (p+r)/2; Sort(a,p,q); Sort(a,q+1,r); Merge(a,p,q,r); } } Merge(a,p,q,r) { i=0; j=p; while (j<=q) b[i++]=a[j++];
i=0; k=p; Který z algoritmů je snazší na napsání? while (k<j && j<=r) if (b[i]<=a[j]) Který z algoritmů je rychlejší? a[k++]=b[i++]; else a[k++]=a[j++]; while (k<j) ...
3/41
Algoritmická složitost ► Složitost
algoritmu se většinou měří na „imaginárním“ počítači
►
Všechny operace stejně dlouhé
►
Každá položka zabírá v paměti stejné místo
► Naproti ►
►
tomu v reálném počítači
Operace trvají různě dlouhou dobu ►
operace porovnávání reálných čísel
►
operace přesunu v paměti
►
goniometrické funkce
Operace majoritní a „šumové“ ►
např. u cyklu – operace s indexy a kontrola hranic je zanedbatelná, operace uvnitř cyklu jsou podstatné 4/41
Algoritmické složitosti ► Složitosti
algoritmu
►
Paměťová
►
Časová
►
Algoritmická
► Kritéria
složitosti
►
Počet časově náročných operací (porovnání, přesun, …)
►
Počet obsazených paměťových míst
5/41
Asymptotické složitosti ► Při
návrhu algoritmu se uvažuje spíše asymptotická složitost
►
Odhad složitosti pro dostatečně velkou množinu vstupních dat
►
Např. pro vyřešení problému s n vstupními daty potřebujeme T(n) = 5n2 + 4n + 50 časových jednotek
►
Protože uvažujeme velké n jsou nižší řády zanedbatelné (stejně jako konstanty)
►
Výsledná složitost je tedy T(n) ∈ O(n2)
6/41
Asymptotické složitosti ► Pro
malá n nemusí být algoritmus s nižší složitostí nutně rychlejší
►
Např. n2 vs. 50n + 500 10000 50.n + 500 n.n
9000 8000 7000 6000 5000 4000 3000 2000 1000 0 0
10
20
30
40
50
60
70
80
90
100
7/41
Asymptotické složitosti ► Vyhodnocení ►
►
složitostí
Nejhorší možný případ O(g(n)) ►
Nejhorší možná kombinace vstupních dat (např. posloupnost seřazená opačně)
►
Lidsky: pro žádnou množinu dat to nebude trvat déle než g(n)
Nejlepší možný případ Ω(g(n)) ►
Nejlepší možná kombinace vstupních dat (např. seřazená posloupnost)
►
Lidsky: problém nepůjde vyřešit rychleji než v g(n) krocích
8/41
Asymptotické složitosti ►
Pokud je algoritmus omezen shora i zdola značíme Θ(g(n))
►
Průměrný případ ►
Jak algoritmus dopadá průměrně pro všechny kombinace vstupních dat
►
Složité na určení – používají se pravděpodobnosti
9/41
Asymptotické složitosti ► Běžné
složitosti
►
O(1) – konstantní počet kroků
►
O(log N) – logaritmický počet kroků
►
O(N) – lineární počet kroků
►
O(N log N)
►
O(N2) – kvadratický počet kroků
►
O(2N) – exponenciální počet kroků
Asymptotické složitosti ► Proč ►
se tím vůbec zabývat?
počítač vykoná 1 milion operací/s
n f(n)
20
40
60
80
100
500
1000
n
20μs
40μs
60μs
80μs
0.1ms
0.5ms
1ms
n log n
86μs
0.2ms
0.35ms
0.5ms
0.7ms
4.5ms
10ms
n2
0.4ms
1.6ms
3.6ms
6.4ms
10ms
0.25s
1s
n3
8ms
64ms
0.22s
0.5s
1s
125s
17min
2n
1s
n!
77tis.let
11.7dní 36tis.let
Třídy složitostí ►P
– problém může být vyřešen v polynomiálním čase na deterministickém počítači
►
Např. vyhledávání
► NP
– problém může být vyřešen v polynomiálním čase na nedeterministickém počítači
12/41
Třídy složitostí ► NP
úplný – nejtěžší problémy z NP (lze na ně v polynomiálním čase převést všechny NP problémy)
►
Jeden z největších problémů tisíciletí: za nalezení odpovědi zda je možné převést NP – úplný na P odměna $ 1 000 000
►
Např. hledání hamiltonovské kružnice
►
Součet podmnožiny
Třídy složitostí ►
Součet podmnožiny ►
Dána množina { −7, −3, −2, 5, 8}
►
Zjistěte, zda součet jakékoliv podmnožiny se rovná 0
►
Testujeme: ►
všechny samostatné prvky: n (5) všechny dvojice: (n2) (10)
►
všechny trojice: (n3) (10)
►
...
►
►
Pro ► ► ► ►
n=3: 7 n=4: 15 n=5: 31 n=10: 1023
n 2: n 2: n 3: n 4:
9 16 125 10000
Třídy ►
Dána množina { −7, −3, −2, 5, 8}
►
Zjistěte, zda součet jakékoliv podmnožiny se rovná 0
►
ANO: { −3, −2, 5}
Analýza algoritmu ► Příklad
(dvě řazení pole)
Sort(a,n) { for(i=1; i=1)&&(a[j]>t)) { a[j+1]=a[j]; j=j-1; } a[j+1]=t; } }
operace
opakování
3
n
2 2 4
n-1 n-1 sum(ti+1)
4 2
sum(ti) sum(ti)
3
n-1
T(n) = 14n + 10 sum(ti) – 11 nejhorší T(n) = 5n2 + 19n - 21
16/41
Analýza algoritmu ► Příklad
(dvě řazení pole)
T(n) ≤ 2T(n/2) + 2n T(n) ≤ 2n log n
Sort(a,p,r) { if(r>p) { q = (p+r)/2; Sort(a,p,q); Sort(a,q+1,r); Merge(a,p,q,r); } } Merge(a,p,q,r) { i=0; j=p; while (j<=q) b[i++]=a[j++]; i=0; k=p; while (k<j && j<=r) if (b[i]<=a[j]) a[k++]=b[i++]; else a[k++]=a[j++]; while (k<j) ... 17/41
Analýza algoritmu ► Příklad
(dvě řazení pole)
►
řazení 1: T(n) ∈ O(n2)
►
řazení 2: T(n) ∈ O(n log n)
18/41
Úlohy ► Jaké ►
►
►
úlohy můžeme řešit
Off-line úlohy ►
všechna data známe už při spuštění algoritmu
►
např. seřazení pole
On-line úlohy ►
data přicházejí v diskrétních časových okamžicích
►
mezivýsledky musí být k dipozici než přijdou další data
►
např. řazení uživatelem modifikovaného pole
Real-time úlohy ►
nejtěžší – data přicházejí průběžně, odezva musí být okamžitá
►
např. řazení hodnot z měřícího zařízení do pole 19/41
Návrhy algoritmů ► Řešení
hrubou silou (brute force)
►
Přímočaré řešení problému
►
Zřídkakdy bývá řešení efektivní
►
Často pouze pro první „nástřel“
►
Příklady: ►
Lineární vyhledávání v poli
►
Řazení pole metodou přímého vkládání
►
Součet posloupnosti čísel prostým sčítáním
20/41
Návrhy algoritmů ►
Součet posloupnosti čísel (hrubá síla) for(i = od; i<do; i++) suma = suma + i;
►
Součet posloupnosti čísel suma = ((do – od + 1)*(od + do))/2;
►
O(n) -> O(1) !!!
21/41
Návrhy algoritmů ► Rozděl ►
►
a panuj (divide and conquer)
Velmi známý a často používaný přístup ►
Rozdělení vstupních dat na několik podproblémů
►
Pokračovat v dělení až na dostatečně malé problémy
►
Dostatečně malé problémy vyřešit známou metodou
►
Poskládat dílčí řešení do celku
Příklady ►
Mergesort
►
Quicksort
►
Fast Fourier Transformation (zpracování signálu)
►
Vyhledávání půlením intervalu
►
Nalezení mediánu 22/41
Návrh algoritmů ► Náhodné
rozložení (randomization)
►
Než začneme s daty pracovat, náhodně je upravíme
►
V některých případech může nevhodná kombinace dat vést k nárůstů potřebného času
►
Např. pro vyhledávání se velmi často používá binární strom, v nejjednodušší verzi konstruovaný tak, že nový prvek přidáme tak, aby vždy splňoval kritéria < >
23/41
Návrh algoritmů ►
Příklad binárního stromu ►
Pro posloupnost: 12, 8, 3, 10, 15, 18, 19 12
8
3
15
10
18
19 ►
Co se stane když na vstupu bude seřazená sekvence? 24/41
Návrh algoritmů ►
Příklad binárního stromu ►
Pro posloupnost: 3, 8, 10, 12, 15, 18, 19 3 8 10 12 15 18 19
►
Výhoda pro vyhledávání zmizela... 25/41
Návrh algoritmů ► Hladové
algoritmy (greedy)
►
Vybírají vždy tu možnost, která se v dané chvíli jeví jako nejlepší
►
Nikdy se nevrací ve volbě zpět
►
Např. ►
Nalezení minimální kostry v grafu
►
Huffmanovo kódování
26/41
Návrh algoritmů ►
Huffmanovo kódování ►
Chceme poslat množinu znaků co nejkratším počtem bitů (např. na pomalé síti)
►
Při posílání standardním způsobem zabírá každý znak 8(7) bitů, některé znaky však používáme málo nebo dokonce vůbec
►
Ideální stav – frekventovaná písmena musí být co nejkratší a naopak
►
Slovo: OLOVO můžeme zakódovat např. jako 010011010 a přiložit tabulku: O (0), L (10), V (11)
►
Jednoduchým algoritmem můžeme řetězec dekódovat tak, že vždy vezmeme největší možný kus kódu
►
O L O V O 0 10 0 11 0 27/41
Návrh algoritmů ►
Huffmanovo kódování ►
Zkusme odeslat slovo OLOVENY
►
Tabulku musíme rozšířit o 3 písmena E (01), N (001), Y (011)
►
Zakódované slovo je tedy 01001101001011
►
Zkusíme-li slovo znovu dekódovat, čeká nás nemilé překvapení...
►
►
O L Y O L E Y 0 10 011 0 10 01 011 Kde se stala chyba?
28/41
Návrh algoritmů ►
Huffmanovo kódování ►
Aby bylo možné slova jednoznačně dekódovat, nesmí žádný znak obsahovat na svém začátku znak jiný
►
V předchozím příkladu O (0) je začátkem (prefixem) E (01)
►
Jak tomu zabránit? ►
vytvořit si binární strom, písmena mohou být pouze v listech 0 0 O
1 0
1 L
0 V
►
1 0
1 E
N
1 Y
Zakódované slovo: 000100100101110111 29/41
Návrh algoritmů ► Dynamické ►
►
programování
Základní charakteristiky ►
Prohledávání velké množiny pro nalezení optima
►
Optimální řešení může být vyjádřeno jako složení optimálních řešení podproblémů
►
Počet podproblémů je relativně malý
Často pro řešení kombinatorických úloh
30/41
Návrh algoritmů ► Lokální
vyhledávání (local search)
►
Algoritmu se na vstup musí dát odhad požadovaného řešení
►
Prohledáváním sousedů iterativním způsobem je toto řešení dále zpřesňováno
►
Algoritmus končí v okamžiku, kdy se dvě po sobě jdoucí iterace liší pouze o malou hodnotu
►
Typičtí zástupci ►
Simulované žíhání
►
Genetické algoritmy
►
Neuronové sítě
31/41
Návrh algoritmů ►
Příklad ►
Hledání kořenů kvadratické rovnice Newtonovou metodou ►
Hlavní myšlenka: Nejprve se nalezne odhad kořene V každém kroku se vypočte tečna funkce v odhadnutém bodě Průsečík tečny a osy x se použije jako nový odhad
32/41
Urychlování algoritmů ► Optimalizace
kódu
►
Dnes už není tak důležitá (překladače dělají spoustu práce za vás)
►
Zásady: ►
Neprovádět opakovaně v cyklu to, co se dá provést před ním - vyjmutí před cyklus
►
Optimalizovat tělo cyklu
►
Používat předchozí výsledky
►
Využívat speciálních vlastnosti problému
33/41
Urychlování algoritmů ► Vyjmutí
před cyklus
for(i=0; i
► Optimalizace t = cos(arg); for(i=0; i
34/41
●
Urychlování algoritmů
► Optimalizace
těla cyklu
for(i=0; i
► Optimalizace for(i=0; i
35/41
Urychlování algoritmů ► Použití
předchozích výsledků
for(i=0; i
► Optimalizace t = 1; for(i=0; i
36/41
Urychlování algoritmů ► Využití ►
vlastností problému
Viz. příklad u brutální síly – součet řady
37/41
Snížení složitosti problému ► Předzpracování ►
dat
Při velkém množství opakování nějaké operace můžeme data uspořádat nebo vytvořit pomocné struktury, které problém usnadní
► Příklady ►
Vyhledávání – setřídíme posloupnost ►
Z K*O(n) -> O(n log n) + K*O(log n)
►
čím vyšší K, tím vyšší úspora
38/41
Snížení složitosti problému ► Příklady ►
Vyhledávání oblasti – dělení prostoru ►
Zjišťování zda bod leží uvnitř nějakého obdélníku
39/41
Snížení složitosti problému ► Většinou
za snížení složitosti zaplatíme zvýšenou spotřebou paměti nebo naopak
► Ne
vždy je možné složitost snížit
40/41
Konec
41/41
