Kľúčové slová: paměťová a časová složitost, asymptotická časová složitost, určování časové složitosti

• zložitosť algoritmov sa delí na časovú a priestorovú (+ komunikační - skripta IZP).
  1. časová zložitosť sa zaoberá časom potrebným na vyriešenie daného problému
  2. priestorová sa zaoberá potrebou pamäti
     • prostorou složitost lze zmenšit na úkor časové a naopak
  3. 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
  • ⇒ z toho získáváme horní a dolní odhad složitosti algoritmu a průměrnou (očekávanou) složitost

• zaujíma nás chovanie danej metódy až do bodu pre N blížiace sa nekonečnu. Na jej základe môžme porovnávať rýchlosť rôznych algoritmov
• 3 zložitosti:
  • Omikron - horná hranica chovania (worst case, najpoužívanejšie)
  • Omega - dolná hranica chovania
  • Théta - vyjadruje triedu chovania (chovanie nikdy nie je horšie ani lepšie ako táto trieda)

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

• c g(n) - funkcia zložitosti Omikron - časová asymptotická složitost algoritmu
• f(n) - reálna funkcia priebehu daného algoritmu

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

• 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

• c g(n) - funkcia zložitosti Omega
• f(n) - reálna funkcia priebehu daného algoritmu

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

• 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í

• c1 g(n), c2 g(n) - funkcie zložitosti Théta
• f(n) - reálna funkcia priebehu daného algoritmu

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

1. exaktní
   • spočítáme to přesně - je třeba najít nejhorší možný vzorek dat a nejlepší a počet všech možných vstupů
   • lze ovšem i určit řád složitosti ⇒ nepočítají se přesně „všechny drobný“
2. neformální analýza
   • slouží k porovnávání složitostí algoritmů

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

• 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ť