V tomto kurzu se dozvíte, co jsou asymptotické notace. Dozvíte se také o notaci Big-O, Theta a Omega.
Efektivita algoritmu závisí na množství času, úložiště a dalších zdrojích potřebných k provedení algoritmu. Účinnost se měří pomocí asymptotických notací.
Algoritmus nemusí mít stejný výkon pro různé typy vstupů. S nárůstem velikosti vstupu se výkon změní.
Studie změny výkonu algoritmu se změnou v pořadí velikosti vstupu je definována jako asymptotická analýza.
Asymptotické notace
Asymptotické notace jsou matematické notace používané k popisu doby chodu algoritmu, když má vstup sklon k určité hodnotě nebo k mezní hodnotě.
Například: V bublinovém třídění, když je vstupní pole již tříděno, je doba potřebná algoritmu lineární, tj. V nejlepším případě.
Když je ale vstupní pole v obráceném stavu, algoritmu trvá maximální čas (kvadraticky) seřadit prvky, tj. Nejhorší případ.
Když vstupní pole není ani tříděno, ani v opačném pořadí, pak to trvá průměrně. Tyto doby trvání jsou označeny pomocí asymptotických notací.
Existují hlavně tři asymptotické notace:
- Big-O notace
- Omega notace
- Theta notace
Big-O notace (O-notace)
Big-O notace představuje horní hranici doby běhu algoritmu. Poskytuje tedy nejhorší složitost algoritmu.
Big-O dává horní mez funkce
O (g (n)) = (f (n): existují pozitivní konstanty c a n 0 takové, že 0 ≦ f (n) ≦ cg (n) pro všechna n ≧ n 0 )
Výše uvedený výraz lze popsat jako funkce f(n)patřící do množiny, O(g(n))pokud existuje kladná konstanta ctak, že leží mezi 0a cg(n)pro dostatečně velkou n.
U libovolné hodnoty ndoba běhu algoritmu nepřekročí čas poskytovaný O(g(n)).
Protože poskytuje nejhorší dobu chodu algoritmu, je široce používán k analýze algoritmu, protože nás vždy zajímá nejhorší scénář.
Omega notace (Ω-notace)
Omega notace představuje spodní hranici doby běhu algoritmu. Poskytuje tedy nejlepší složitost algoritmu.
Omega udává dolní mez funkce
Ω (g (n)) = (f (n): existují kladné konstanty c a n 0 takové, že 0 ≦ cg (n) ≦ f (n) pro všechna n ≧ n 0 )
Výše uvedený výraz lze popsat jako funkce f(n)patřící do množiny, Ω(g(n))pokud existuje kladná konstanta ctak, že leží výše cg(n), pro dostatečně velkou n.
Pro jakoukoli hodnotu nje minimální čas vyžadovaný algoritmem dán společností Omega Ω(g(n)).
Theta notace (Θ-notace)
Theta notace obklopuje funkci shora a zdola. Jelikož představuje horní a dolní mez doby běhu algoritmu, používá se k analýze průměrné složitosti algoritmu.
Theta ohraničuje funkci v rámci faktorů konstant
Pro funkci g(n), Θ(g(n))je dána vztahem:
Θ (g (n)) = (f (n): existují pozitivní konstanty c 1 , c 2 a n 0 takové, že 0 ≦ c 1 g (n) ≦ f (n) ≦ c 2 g (n) pro všechny n ≧ n 0 )
Výše uvedený výraz lze popsat jako funkce f(n)patřící do množiny, Θ(g(n))pokud existují kladné konstanty a taková, že může být vložena mezi a pro dostatečně velké n.c1c2c1g(n)c2g(n)
Pokud funkce f(n)leží kdekoli mezi a pro všechny , pak se říká, že je asymptoticky pevně svázaná.c1g(n)c2g(n)n ≧ n0f(n)
