http://xoax.net/comp/sci/algorithms/Lesson6.php

Pro hodnocení kvality algoritmu i pro porovnání dvou různých algoritmů jsou zapotřebí vhodná kriteria. Účelnými parametry jsou čas potřebný pro provedení algoritmu a paměťový prostor, který zaujímá program a jeho data. Čas i prostor potřebný pro algoritmus závisí na velikosti zpracovávaných dat. Proto má složitost nejčastěji podobu funkce velikosti zpracovávaných dat, udávané počtem položek N.

Jedná se o nejčastější hodnotící kritérium algoritmů. Vyjadřuje se porovnáním algoritmu s určitou funkcí pro N blížící se nekonečnu. Porovnávání má podobu tří různých složitostí.

• O – Omikron (velké O, O, big O) – horní hranice chování
• Ω – Omega – dolní hranice chování
• Θ – Theta – vyjadřuje třídu chování

Big O notation

Taková složitost vyjadřuje horní hranici časového chování algoritmu. O(g(n)) označuje množinu funkcí f(n), pro které platí:

{f(n) : ∃(c>0, n0>0) takové, že ∀(n>=n0) platí [0<=f(n)<=c*g(n)]}

kde c a n0 jsou jisté vhodné kladné konstanty. Pak zápis f(n)=O(g(n)), označuje, že funkce f(n) roste maximálně tak rychle jako funkce g(n). Funkce g(n) je horní hranicí množiny takových funkcí, určené zápisem O(g(n)).

Složitost Ω vyjadřuje dolní hranici časového chování algoritmu. Ω(g(n)) označuje množinu všech funkcí f(n) pro které platí:

{f(n) : ∃(c>0, n0>0) takové, že ∀n>=n0 platí [0<=c*g(n)<=f(n)]}

kde c a n0 jsou určité vhodné kladné konstanty. Pak zápis f(n)=(Ω(g(n))) označuje, že funkce f(n) roste minimálně tak rychle, jako funkce g(n). Funkce g(n) je dolní hranicí množiny všech funkcí, určených zápisem (Ω(g(n))).

Složitost Θ¹⁾ vyjadřuje třídu časového chování algoritmu. Θ(g(n)) označuje množinu všech funkcí f(n), pro něž platí:

{f(n) : ∃(c1>0, c2>0, n0>0) takové, že ∀(n>=n0) platí [0<=c1*g(n)<=f(n)<=c2*g(n)]}

kde c1, c2 and n0 jsou vhodné kladné konstanty. Složitost vyjádřená zápisem Theta (Θ) označuje časové chování shodné jako daná funkce. Pak zápis f(n)= Θ(g(n)) označuje, že funkce f(n) roste tak rychle jako funkce g(n). Funkce g(n) vyjadřuje horní a současně dolní hranici množiny funkcí, označených zápisem Θ(g(n)).

1. Θ(1) je označení algoritmů s konstantní časovou složitostí. Např. indexování prvků v poli.
2. Θ(log(n)) je označení algoritmů s logaritmickou časovou složitostí. Základ logaritmu není podstatný, protože hodnoty logaritmu pro různé základy se liší pouze konstantou vzájemného převodu. Logaritmickou složitostí se vyznačují např. rychlé vyhledávací algoritmy (půlení intervalů v seřazeném seznamu).
3. Θ(n) je označení algoritmů s lineární časovou složitostí. Tuto složitost mají běžné vyhledávací algoritmy (hlednání v neseřazeném poli) a řada algoritmů sekvenčně zpracovávajících datové struktury.
4. Θ(n*log(n)) je označení algoritmů nazývané také linearitmické. Tuto časovou složitost mají např. rychlé řadicí algoritmy (quicksort).
5. Θ(n²) je označení algoritmů s kvadratickou časovou složitostí. Takovou časovou složitostí se vyznačují algoritmy sestavené z dvojnásobného počítaného cyklu do n. Patří mezi ně řada klasických řadicích algoritmů (bubblesort).
6. Θ(n³) je označení algoritmů s kubickou časovou složitostí. Algoritmy s touto časovou složitostí jsou prakticky použitelné především pro málo rozsáhlé problémy. Kdykoli se n zdvojnásobí, čas zpracování je osminásobný.
7. Θ(kⁿ), kde k je reálné kladné číslo, je označení algoritmů s exponenciální (pro k=2 binomickou) časovou složitostí. Existuje několik prakticky použitelných algoritmů s touto složitostí. Velmi často se označují jako algoritmy pracující s “hrubou silou” (brute-force algorithms). Když u binomické časové složitosti n vzroste o 1, čas se zdvojnásobí.

Při určování časové složitosti je třeba vyjít ze složitostí popsaných v klasifikaci algoritmů výše. Dále musíme vzít v úvahu, zda je daný algoritmus řešitelný. Příklad neřešitelného algoritmu – algoritmus, který by rozhodnul, zda nějaký algoritmus skončí po určitém počtu kroků nebo ne.

• casová a paměťová náročnost
• asymptotická složitost: omikron (vrchní), omega (spodní), theta (třída chování)
• třídy: konstantní, lineární, logaritmická, linearirmická, kvadratická, kubická, exponenciální
• řešitelnost algoritmu, přířazení do třídy, matematicky: turingův stroj, nebo prostě studiem algoritmu