29 - Hodnocení složitosti algoritmů
Kľúčové slová: paměťová a časová složitost, asymptotická časová složitost, určování časové složitosti
Úvod
zložitosť algoritmov sa delí na časovú a priestorovú (+ komunikační - skripta IZP).
časová zložitosť sa zaoberá časom potrebným na vyriešenie daného problému
priestorová sa zaoberá potrebou pamäti
komunikační složitost - množství dat vyměněných mezi různými počítači při distribuovaném výpočtu
závisí na velikosti vstupních dat, proto ji můžeme popsat jako funkci T(n), kde číslo n udává velikost vstupních dat (např. linární: T(n) = an + b)
a je multiplikativní konstanta - počet operací ve strojovém kódu, který je třeba provést pro vyřešení jedné operace na úrovni vyššího programovacího jazyka
b je aditivní konstanta - udává konstantní nárůst složitosti nezávislý na velikosti vstupních dat (závisí na počítačovém systému)
při značné velikosti vstupních dat můžeme konstanty zanedbat
pokud vybereme největší konstantu a (z možných konstant a), označíme ji c, platí, že T(n) ≤ cn pro všechna dostatečně velká n ⇒ tuto skutečnost označíme jako T = O(n) - asymptotické chování funkce T, kde jsou zanedbány konstanty a a b, a kde nás zajímá chování pro vysokou hodnotu n
-
Asympotická zložitosť
Zložitosť Omikron (Big O, O)
existuje funkcia O(g(n)), pre ktorú platí, že priebeh funkcie f(n) (časová funkcia daného programu) je rastúci maximálne tak rýchlo ako g(n).
používa sa najčastejšie ⇒ udává složitost algoritmu v nejhorším případě (složitost pro nejhorší vstup)
Pre záujemcov ešte matematické vyjadrenie:
{f(n): Exist(c > 0, n0 > 0) takové, že ForAll n > n0 platí [0 ⇐ f(n) ⇐ c*g(n)]}
Zložitosť Omega
komplementárna funkcia k Omikron
funkcia f(n) rastie minimálne tak rýchlo ako Omega(g(n))
používa sa málo ⇒ ideální složitost daného algoritmu (nejrychlejší možné provedení), která nastává jen pro určité případy vstupních
dat
Pre záujemcov ešte matematické vyjadrenie:
{f(n): Exist(c > 0, n0 > 0) takové, že ForAll n > n0 platí [0 ⇐ c*g(n) ⇐ f(n)]}
Zložitosť Théta
vyjadruje časové chovanie rovnaké ako daná funkcia
funkcia f(n) rastie tak rýchlo ako Théta(g(n))
počítá se jako střední hodnota náhodné složitosti T(n) při určitém rozložení vstupních dat
je to složitost pro běžný vstup ⇒ vypočítá se na základě pravděpodobnosti výskytu určitých vstupních dat a odpovídajících složitostí
Pre záujemcov ešte matematické vyjadrenie:
{f(n): Exist(c1 > 0, c2 > 0, n0 > 0) takové, že ForAll (n > n0) platí [0 ⇐ c1*g(n) ⇐ f(n) ⇐ c2*g(n)]}
Zjišťování složitostí
exaktní
neformální analýza
Klasifikácia algoritmov
Théta(1) - algoritmy s konštantnou časovou zložitosťou
Théta(lg(n)) - algoritmy s logaritmickou časovou zložitosťou (rýchle vyhľadávacie algoritmy)
Théta(n) - algoritmy s lineárnou časovou zložitosťou (bežné vyhľadávacie algoritmy, algoritmy, ktoré sekvenčne spracovávajú dátové štruktúry)
Théta(n*lg(n)) - algoritmy s linearitmickou časovou zložitosťou (rýchle „řadicí“ algoritmy)
Théta(n*n) - algoritmy s kvadratickou zložitosťou (bežné „řadicí“ algoritmy, napr. bublinové „řazení“)
Théta(n*n*n) - algoritmy s kubickou časovou zložitosťou. Prakticky použiteľné len pre málo rozsiahle problémy.
Théta(k^n) - algoritmy s exponenciálnou (pre n=2 - binomickou) zložitosťou. (brute-force algoritmy)
Jednotlivé algoritmy:
Binárne vyhľadávanie v zoradenom poli - log(n)
Dijkstrova varianta binárneho vyhľadávania - log(n)
Vyhľadávanie v AVL stromoch - log(n)
Select sort - kvadratická časová zložitosť
Bubble sort - kvadratická časová zložitosť (ale najrýchlejšia metóda v prípade už zoradeného poľa)
Heap sort - linearitmická časová zložitosť
Bublinové vkládání (Bubble insert sort) - kvadratická časová zložitosť
Quick sort - linearitmická časová zložitosť
Radix sort - lineárna časová zložitosť
Poznámka k priestorovej zložitosti: algoritmy „in situ“ - nepotrebujeme žiadne miesto navyše.
Zdroj
Potvrzení
29 |
Celé jméno | OK | !!! |
roman jasho | | |
Jirka Hynek | | |
| 2 | |