Wikipedie

Asymptotická složitost: Porovnání verzí

Interaktivně procházet historii
← Přejít na předchozí porovnáníPřejít na další porovnání →
Smazaný obsah Přidaný obsah
VizuálníWikitext
Přepsání části s příklady časových složitostí do tabulky.
Vyhození textu přesunutého do článku "Landauova notace"
Řádek 1:
{{rozdělit|na článek [[Landauova notace]] o matematickém konceptu a na článek [[asymptotická složitost]] pojednávající o složitosti}}
 
Při řešení úloh pomocí výpočetní techniky musíme mít nástroj, kterým dokážeme porovnat efektivitu a rychlost vykonávání jednotlivých algoritmů. Pro tento účel byly zavedeny pojmy '''asymptotická složitost''' a '''operační náročnost algoritmu'''.
 
'''Asymptotická složitost''' je způsob klasifikace počítačových [[algoritmus|algoritmů]]. Určuje operační náročnost algoritmu tak, že zjišťuje jakým způsobem se bude chování algoritmu měnit v závislosti na změně velikosti (počtu) vstupních dat. Zapisuje se pomocí [[Landauova notace|Landauovy notace]] (též „Omikron notace“, nebo („velké O notace“) jako <math>O(f(N))</math> (např. <math>O(N)</math>). Obvykle se používá asymptotická časová a prostorová složitost.
 
Používaný zápis znamená, že náročnost algoritmu je menší než <math>A + B \cdot f(N)</math>, kde <math>A</math> a <math>B</math> jsou vhodně zvolené konstanty a <math>N</math> je veličina popisující velikost vstupních dat. Zanedbáváme tedy multiplikativní i aditivní konstanty, tzn. <math>O(N + 1000) = O(1000 \cdot N) = O(N)</math>. Zajímá nás jen chování funkce pro velké hodnoty <math>N</math>.
Řádek 66 ⟶ 64:
 
Existují i funkce, u nichž nelze složitost vůbec shora rozumně omezit. Příkladem budiž [[Ackermannova funkce]].
 
== Formální definice ==
 
Nechť <math>f(x)</math> a <math>g(x)</math> jsou dvě funkce definované na nějaké podmnožině [[Reálné číslo|reálných čísel]].
Potom řekneme, že
 
:<math>f(x) \in \mathcal{O}(g(x))</math>
právě tehdy když
:<math>\exists (C>0), x_0 : \forall(x>x_0) \; |f(x)| \leq |Cg(x)|</math>
 
== Další používané notace ==
 
{|class="wikitable"
!Notace
!Význam
!Definice
<!-- !Alternative definition -->
|-
|<math>f(x) \in \mathcal{O}(g(x))</math>
|<math>f</math> je asymptoticky ohraničena funkcí <math>g</math> shora (až na konstantu)
<!-- |<math>\limsup_{x \to \infty} \left|\frac{f(x)}{g(x)}\right| < \infty</math> -->
|<math>\exists (C>0), x_0 : \forall(x>x_0) \; |f(x)| \leq |Cg(x)|</math>
|-
|<math>f(x) \in \Omega(g(x))</math>
|<math>f</math> je asymptoticky ohraničena funkcí <math>g</math> zdola (až na konstantu)
<!--|<math>\liminf_{x \to \infty} \left|\frac{f(x)}{g(x)}\right| > 0 </math> -->
|<math>\exists (C>0), x_0 : \forall (x>x_0) \; |Cg(x)| \leq |f(x)|</math>
|-
|<math>f(x) \in \Theta(g(x))</math>
|<math>f</math> je asymptoticky ohraničena funkcí <math>g</math> z obou stran (až na konstantu)
<!-- |<math>0 < \liminf_{x \to \infty} \left|\frac{f(x)}{g(x)}\right| \leq \limsup_{x \to \infty} \left|\frac{f(x)}{g(x)}\right|< \infty</math> -->
<!--|<math>f(x) \in O(g(x)) \cap \Omega(g(x))</math> -->
|<math>\exists (C,C'>0), x_0 : \forall (x>x_0) \; |Cg(x)| < |f(x)| < |C'g(x)| </math>
|-
|<math>f(x) \in o(g(x))</math>
|<math>f</math> je asymptoticky ohraničena funkcí <math>g</math> shora ostře
<!-- |<math>\lim_{x \to \infty} \left|\frac{f(x)}{g(x)}\right| = 0</math> -->
<!-- |<math>\forall \;\epsilon>0,\exists \;x(\epsilon) : |f(x)| < \; \epsilon |g(x)|, \forall x>x(\epsilon).</math> -->
|<math>\forall (C>0),\exists x_0 : \forall(x>x_0) \; |f(x)| < |Cg(x)|</math>
|-
|<math>f(x) \in \omega(g(x))</math>
|<math>f</math> je asymptoticky ohraničena funkcí <math>g</math> zdola ostře
<!-- |<math>\lim_{x \to \infty} \left|\frac{f(x)}{g(x)}\right| = \infty</math> -->
|<math>\forall (C>0),\exists x_0 : \forall(x>x_0) \; |Cg(x)| < |f(x)|</math>
|-
|<math>f(x)~\sim g(x)</math>
|asymptoticky rovné
|<math>\lim_{x \to \infty} \frac{f(x)}{g(x)} = 1</math>
|}
 
=== Vztahy mezi množinami ===
 
<math>\Theta(g(x)) = \mathcal{O}(g(x)) \cap \Omega(g(x))</math><br />
<math>\Theta(g(x)) = \mathcal{O}(g(x)) \smallsetminus o(g(x))</math><br />
<math>\Theta(g(x)) = \Omega(g(x)) \smallsetminus \omega(g(x))</math><br />
 
== Snižování výpočetní složitosti algoritmů ==
Řádek 186 ⟶ 129:
Podobný případ je, když asymptoticky lepší algoritmus A má větší multiplikativní konstantu než alg. A*, ale v důsledku toho je pro reálně používané, tj. dostatečně malé, velikosti dat výhodnější A*, protože A* má menší režii.
 
== Externí odkazyOdkazy ==
 
=== Související články ===
 
* [[Landauova notace]]
 
=== Externí odkazy ===
 
*[http://wiki.matfyz.cz/index.php?title=St%C3%A1tnice_-_Odhady_slo%C5%BEitosti Odhady složitosti] {{cs}}
Citováno z „https://cs.wikipedia.org/wiki/Asymptotická_složitost“