Vyčíslitelnost a složitost výpočtů Asymptotiky Asymptotiky •V informatice se asymptotika používá k odhadu časové a prostorové složitosti algoritmů. •Porovnání efektivity algoritmů a výběr toho nejlepšího pro konkrétní problém. •Zajištění škálovatelnosti systémů při růstu dat. • • Asymptotiky •Nejhorší případ (worst-case) •Průměrný případ (average-case) •Nejlepší případ (best-case) •Bubble Sort: •Nejhorší případ: prvky jsou seřazeny v opačném pořadí. •Průměrný případ: je třeba provést mnoho porovnání. •Nejlepší případ: prvky jsou již seřazené. • Asymptotiky •Základní principy asymptotik: •Ignorování konstant a menších členů •Při porovnávání růstu funkcí asymptoticky nehrají roli aditivní ani multiplikativní konstanty. •Např. f(x)=x+100, g(x) = x // f(x)=5x,g(x)=x •Důraz na chování funkcí pro velké hodnoty argumentu •Asymptotika se zaměřuje na růst funkcí pro velké vstupy. Chování funkcí pro malé hodnoty argumentu je ignorováno. •Například funkce 2x/10 roste pro malé x (mezi 1 a 10) pomaleji než x2, ale pro velká x ji x2 předčí. • • • • Asymptotiky •f(x)=O(g(x)): Funkce f(x) roste nejvýše tak rychle jako g(x). (Horní odhad růstu.) •f(x)=Ω(g(x)): Funkce f(x) roste nejméně tak rychle jako g(x). (Dolní odhad růstu.) •f(x)=Θ(g(x)): Funkce f(x) a g(x) rostou stejně rychle. (Funkce mají stejnou asymptotickou rychlost růstu.) •f(x)=o(g(x)): Funkce f(x)roste pomaleji než g(x). (Rychlost růstu g(x) je větší než u f(x). • Asymptotiky •Pořadí rychlosti růstu funkcí: •Různé typy funkcí mají různé asymptotické rychlosti růstu. Nejčastěji používané funkce v analýze algoritmů seřazujeme podle jejich rychlosti růstu: •Logaritmické funkce: log(x), log₂(x), log₃(x), ... •Tyto funkce rostou velmi pomalu. •Polynomy: x, x², x³, ... •Polynomy rostou rychleji než logaritmické funkce. •Exponenciální funkce: 2ˣ, 3ˣ, 4ˣ, ... •Exponenciální funkce rostou rychleji než polynomy. •Funkce vyššího řádu: 2^(x²), 2^(x³), ... •Tyto funkce rostou extrémně rychle. • Asymptotiky •Odečtení pomaleji rostoucí funkce od rychleji rostoucí: •Pokud od rychleji rostoucí funkce odečteme pomaleji rostoucí funkci, výsledná funkce stále roste stejně rychle jako ta původní, rychleji rostoucí funkce. •Příklad: •Mějme funkce f(x)=x2 a g(x)=x. •Když odečteme g(x) od f(x), tedy f(x)−g(x)=x2, výsledek stále roste asymptoticky stejně rychle jako x2, protože x2 roste mnohem rychleji než x pro velká x. •Funkci x můžeme tedy ignorovat při odhadu asymptotického růstu. • • Asymptotiky •Násobení dvou rostoucích funkcí: •Pokud vynásobíme dvě rostoucí funkce, výsledná funkce poroste rychleji než kterákoliv z původních funkcí. •Příklad: •Mějme funkce f(x)=x a g(x)=log ⁡x. •Pokud je vynásobíme, výsledná funkce bude f(x)⋅g(x)=x log⁡ x. •Funkce x log x roste rychleji než x a také rychleji než log ⁡x. Rychlost růstu této nové funkce je tedy vyšší než rychlost růstu každé z původních funkcí. • Asymptotiky •Sčítání funkcí: •Při sčítání dvou nebo více funkcí se při asymptotické analýze soustředíme na funkci, která roste nejrychleji, protože ta určuje celkovou asymptotickou rychlost růstu výsledné funkce. •Základní pravidlo sčítání funkcí: •Rychlost růstu výsledné funkce odpovídá nejrychleji rostoucí funkci. Ostatní pomaleji rostoucí funkce můžeme asymptoticky ignorovat, protože nemají významný vliv na rychlost růstu pro velké x. •