Vyčíslitelnost a složitost výpočtů 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 •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. • Časová složitost algoritmu Časová složitost algoritmu •Časová složitost algoritmu popisuje, jak se doba běhu algoritmu mění v závislosti na velikosti vstupních dat. •Především u velkých dat. •Časová složitost se obvykle vyjadřuje pomocí tzv. asymptotické notace (Horní odhad růstu). Časová složitost algoritmu •O(1) – Konstanta: •Algoritmus běží vždy ve stejném čase bez ohledu na velikost vstupu. •Příklad: Přístup k prvku v poli pomocí indexu. •O(n) – Lineární: •Doba běhu algoritmu roste přímo úměrně s velikostí vstupu. •Příklad: Prohledání nesetříděného seznamu s n prvky. •O(log n) – Logaritmická: •Časová složitost roste pomaleji než velikost vstupu, což je typické pro algoritmy, které opakovaně dělí problém na menší části. •Příklad: Binární vyhledávání. •O(n log n) – Lineárně logaritmická: •Typická pro efektivní třídicí algoritmy jako je quicksort nebo mergesort. •Časová složitost roste rychleji než lineární, ale pomaleji než kvadratická. • Časová složitost algoritmu •O(n2) – Kvadratická: •Doba běhu roste úměrně druhé mocnině velikosti vstupu. •Příklad: Třídění bublinkou (bubble sort). •O(2n) – Exponenciální: •Časová složitost exponenciálně roste s velikostí vstupu. •Příklad: Rekurzivní řešení problému cestujícího obchodníka. •O(n!) – Faktoriální: •Extrémně náročné algoritmy, kde doba běhu dramaticky roste s velikostí vstupu. •Příklad: Brute-force. Časová složitost algoritmu •1. Identifikace základních operací algoritmu •Každý algoritmus je sestaven z jednotlivých operací, jako jsou: •Přiřazení hodnot proměnným •Podmínky (if-else) •Smyčky (for, while) •Rekurze • Časová složitost algoritmu •2. Analýza smyčky •Smyčky (cykly) mají velký vliv na časovou složitost algoritmu, protože určují, jak často se provádí základní operace. •Jednoduchá smyčka, která běží n krát má časovou složitost O(n). •Smyčka uvnitř smyčky (vnořená smyčka) má složitost násobenou, tj. pro dvě vnořené smyčky, kde každá běží n krát, bude celková složitost O(n²). • Časová složitost algoritmu •3. Podmínky •Podmínky (if-else) mohou mít různé větve, ale z hlediska asymptotické notace se uvažuje vždy ta nejhorší možná větev (worst-case analýza). •Pokud rozhodnutí v podmínce nijak neovlivňuje složitost (provádí se jen jednou), přidává jen O(1) (konstantní složitost). • Časová složitost algoritmu •4. Rekurze •U rekurzivních algoritmů musíte vytvořit tzv. rekurentní vztah a analyzovat ho. •Příklad: •Binární vyhledávání: Rozdělí vstup na polovinu v každém kroku, což vede k O(log n). •Třídění pomocí merge sortu: Rozděluje vstupní seznam a kombinuje je zpět, což vede k O(n log n). • Časová složitost algoritmu Obsah obrázku text, snímek obrazovky, Písmo, číslo Popis se vygeneroval automaticky. •Každým krokem binární vyhledávání dělí seznam na polovinu. Pokud máte pole s n prvky, po prvním kroku zůstane n/2, po druhém kroku n/4, po třetím n/8 atd. Proces pokračuje, dokud není hledaný prvek nalezen nebo nezbyde žádný prvek. •Ano, v případě binárního vyhledávání je skutečně volání rekurze založeno na dělení problému na polovinu •Tento dělicí proces má logaritmický charakter, což znamená, že časová složitost je O(log n). Časová složitost algoritmu Obsah obrázku text, snímek obrazovky, Písmo, číslo Popis se vygeneroval automaticky. •Nejlepší případ (seřazený seznam): O(n) •Průměrný případ: O(n²) •Nejhorší případ (opačně seřazený seznam): O(n²) •což znamená, že celkový počet operací je úměrný n * n = n² Časová složitost algoritmu Obsah obrázku text, snímek obrazovky, Písmo, číslo Popis se vygeneroval automaticky. •Nejlepší případ: O(n) (když je seznam již setříděný) •Průměrný případ: O(n²) •Nejhorší případ: O(n²) Časová složitost algoritmu Obsah obrázku text, snímek obrazovky, Písmo, číslo Popis se vygeneroval automaticky. Obsah obrázku diagram, Plán, řada/pruh, Technický výkres Popis se vygeneroval automaticky. Tato časová složitost se vysvětluje tím, že v průměru se pole při každé iteraci rozdělí přibližně na dvě stejné části, což vytváří log n úrovní rekurzivního volání. Na každé z těchto úrovní probíhá rozdělení pole, které vyžaduje O(n) času, což v celkovém výsledku dává O(n log n). nejhorsi V takovém případě je časová složitost O(n²), protože na každé úrovni zpracováváme n prvků a máme n úrovní. Časová složitost algoritmu Obsah obrázku text, snímek obrazovky, Písmo, číslo Popis se vygeneroval automaticky. Obsah obrázku text, Písmo, bílé, typografie Popis se vygeneroval automaticky. Nejhorší a průměrný případ: O(n²) •Algoritmus má dvě vnořené smyčky: •První smyčka (i) běží přes všechny prvky (n-1 průchodů). •Druhá smyčka (j) hledá nejmenší prvek v zbývající neprohledané části pole (přibližně n-i iterací). •Proto musí Selection sort pro každý prvek v poli najít nejmenší prvek, což vede k celkovému počtu operací n * (n-1) / 2, což je O(n²). •Aritmeticny soucet S=(n−1)×n/2 •V nejhorším i průměrném případě má Selection sort časovou složitost O(n²), protože stále musí porovnávat všechny prvky, i když jsou již seřazeny. 2. Nejlepší případ: O(n²) •Selection sort má také v nejlepším případě časovou složitost O(n²). I když je pole již setříděné, algoritmus stále prohledává zbytek pole, aby našel nejmenší prvek a pokračuje ve výměnách.