====== Hodnocení složitosti algoritmů ======
[[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.

===== Asymptotická složitost =====
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í
<note> Skutečnost, že asymptotická složitost jednoho algoritmu je menší než jiného nemusí znamenat, že pro každé n je první algoritmus rychlejší. Složitost algoritmu vyjadřuje obecné chování třídy algoritmů, čas algoritmu vyjadřuje konkrétní dobu pro jisté N. Pro praktické aplikace se nejčastěji algoritmy charakterizují složitostí O, která vyjadřuje "nejhorší případ" (worst case).</note>

==== Složitost O ====
[[wp>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 Ω ====
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 Θ ====
Složitost Θ((Théta)) 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)).

=== Klasifikace algoritmů ===
  - Θ(1) je označení algoritmů s **konstantní** časovou složitostí. Např. indexování prvků v poli.
  - Θ(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).
  - Θ(//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.
  - Θ(//n//*log(//n//)) je označení algoritmů nazývané také **linearitmické**. Tuto časovou složitost mají např. rychlé řadicí algoritmy (quicksort).
  - Θ(//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).
  - Θ(//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ý.
  - Θ(//k<sup>n</sup>//), 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í.


===== Určování časové složitosti =====
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.

===== Shrnutí =====
  * 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