Asymptotická složitost
náročnost algoritmu při změně velikosti vstupu / From Wikipedia, the free encyclopedia
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 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í Landauovy notace (též „Omikron notace“, nebo „velké O notace“) jako (např. ). Obvykle se používá asymptotická časová a prostorová složitost.
Používaný zápis znamená, že náročnost algoritmu je menší než , kde a jsou vhodně zvolené konstanty a je veličina popisující velikost vstupních dat. Zanedbáváme tedy multiplikativní i aditivní konstanty, tzn. . Zajímá nás jen chování funkce pro velké hodnoty .
Například časová složitost (lineární) říká, že 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 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 naopak na délce vstupu vůbec nezáleží a potřebný čas nepřevýší nějakou pevnou mez. Podobně je tomu i u prostorové složitosti, jen s tou změnou, že se jedná o potřebné paměťové (prostorové) nároky v závislosti na délce vstupních dat.