Asymptotická složitost: Porovnání verzí
Smazaný obsah Přidaný obsah
m + interní odkazy značka: editace z Vizuálního editoru |
Koriguji dvě nepravdivá tvrzení. značka: editace z Vizuálního editoru |
||
Řádek 5:
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é [[Konstanta|konstanty]] a <math>N</math> je [[veličina]] popisující velikost vstupních dat. Zanedbáváme tedy multiplikativní i [[Aditivnost|aditivní]] [[Konstanta|konstanty]], tzn. <math>O(N + 1000) = O(1000 \cdot N) = O(N)</math>. Zajímá nás jen chování [[Funkce (matematika)|funkce]] pro velké hodnoty <math>N</math>.
Například časová složitost <math>O(N)</math> (tzv. lineární) říká, že [[Čas|doba]] trvání práce algoritmu se zvýší přibližně tolikrát, kolikrát se zvýší velikost vstupu. Na druhou stranu u složitosti <math>O(N^2)</math> se doba trvání průběhu zvyšuje kvadraticky, tedy pokud se zvýší délka vstupu dvakrát, potřebný čas se zvýší přibližně čtyřikrát. U časové složitosti <math>O(1)</math> naopak na délce vstupu vůbec nezáleží a potřebný čas
== Třídy složitosti ==
| |||