V tomto návode sa dozviete, čo sú asymptotické notácie. Dozviete sa tiež o notácii Big-O, Theta a Omega.
Účinnosť algoritmu závisí od množstva času, úložného priestoru a ďalších zdrojov potrebných na vykonanie algoritmu. Účinnosť sa meria pomocou asymptotických notácií.
Algoritmus nemusí mať rovnaký výkon pre rôzne typy vstupov. S nárastom veľkosti vstupu sa výkon zmení.
Štúdium zmeny výkonu algoritmu so zmenou v poradí vstupnej veľkosti je definované ako asymptotická analýza.
Asymptotické notácie
Asymptotické notácie sú matematické notácie používané na opis času chodu algoritmu, keď má vstup tendenciu ku konkrétnej hodnote alebo k limitnej hodnote.
Napríklad: V bublinovom triedení, keď je vstupné pole už zoradené, je čas potrebný algoritmom lineárny, tj. V najlepšom prípade.
Ale keď je vstupné pole v opačnom stave, algoritmu trvá maximálny čas (kvadraticky) na triedenie prvkov, tj najhorší prípad.
Ak vstupné pole nie je zoradené ani v opačnom poradí, potom to trvá priemerne dlho. Tieto doby trvania sa označujú pomocou asymptotických značiek.
Existujú hlavne tri asymptotické notácie:
- Zápis Big-O
- Omega notácia
- Theta notácia
Big-O notácia (O-notácia)
Zápis Big-O predstavuje hornú hranicu doby chodu algoritmu. Poskytuje teda najhoršiu zložitosť algoritmu.
Big-O dáva hornú hranicu funkcie
O (g (n)) = (f (n): existujú pozitívne konštanty c a n 0 také, že 0 ≦ f (n) ≦ cg (n) pre všetky n ≧ n 0 )
Vyššie uvedený výraz možno opísať ako funkcia f(n)patriaca do množiny, O(g(n))ak existuje pozitívna konštanta ctaká, že leží medzi 0a cg(n)pre dostatočne veľkú konštantu n.
Pre akúkoľvek hodnotu nprevádzkový čas algoritmu neprekračuje čas poskytnutý parametrom O(g(n)).
Pretože poskytuje najhoršiu dobu chodu algoritmu, je široko používaný na analýzu algoritmu, pretože nás vždy zaujíma najhorší scenár.
Omega notácia (Ω-notácia)
Omega notácia predstavuje dolnú hranicu doby chodu algoritmu. Poskytuje teda najlepšiu zložitosť algoritmu.
Omega dáva dolnú hranicu funkcie
Ω (g (n)) = (f (n): existujú kladné konštanty c a n 0 také, že 0 ≦ cg (n) ≦ f (n) pre všetky n ≧ n 0 )
Vyššie uvedený výraz možno opísať ako funkcia f(n)patriaca do množiny, Ω(g(n))ak existuje kladná konštanta ctaká, že leží vyššie cg(n), a to pre dostatočne veľkú hodnotu n.
Pre každú hodnotu nje minimálny čas požadovaný algoritmom daný programom Omega Ω(g(n)).
Theta notácia (Θ-notácia)
Notácia theta obklopuje funkciu zhora a zdola. Pretože predstavuje hornú a dolnú hranicu doby chodu algoritmu, používa sa na analýzu priemernej zložitosti algoritmu.
Theta ohraničuje funkciu v rámci konštantných faktorov
Pre funkciu g(n), Θ(g(n))je daná vzťahom:
Θ (g (n)) = (f (n): existujú kladné konštanty c 1 , c 2 a n 0 také, že 0 ≦ c 1 g (n) ≦ f (n) ≦ c 2 g (n) pre všetky n ≧ n 0 )
Vyššie uvedený výraz možno opísať ako funkcia f(n)patriaca do množiny, Θ(g(n))ak existujú kladné konštanty a také, ktoré je možné vložiť medzi a pre dostatočne veľké n.c1c2c1g(n)c2g(n)
Ak funkcia f(n)leží kdekoľvek medzi a pre všetkých , potom sa hovorí, že je asymptoticky pevne zviazaná.c1g(n)c2g(n)n ≧ n0f(n)
