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

← Přejít na předchozí porovnání Přejít na další porovnání →

Smazaný obsah Přidaný obsah

V textu

Verze z 7. 12. 2006, 20:29

Asymptotická složitost je způsob klasifikace počítačových algoritmů. Urč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í "velké O notace" (např. O(N)). Obvykle se používá asymptotická časová a prostorová složitost.

Například časová složitost O(N) (tzv. 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 O( $N^{2}$ ) se doba trvání průběhu zvyšuje kvadraticky, tedy pokud se zvýší délka vstupu 2-krát, potřebný čas se zvýší 4-krát. U časové složitosti O(1) naopak na délce vstupu vůbec nezáleží a potřebný čas je stále stejný. 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.

Asymptotická složitost zanedbává jakékoli konstanty, tzn. O(N + 1000) = O(1000 * N) = O(N). Některé asymtotické složitosti mají i své triviální pojmenování (jsou seřazeny od nejrychlejších k nejpomalejším):

O(1) - konstantní
O(log N) - logaritmická
O(N) - lineární
O(N log N) - lineárnělogaritmická
O( $N^{2}$ ) - kvadratická
O( $N^{3}$ ) - kubická
obecně O( $N^{X}$ ) - polynomiální
obecně O( $X^{N}$ ) - exponenciální
O(N!) - faktoriálová

Snižování výpočetní složitosti algortimů

Snahou programátorů je asymptotickou složitost dostat alespoň na polynomiální úroveň, horší složitosti jsou v reálných aplikacích (tedy u vyšších N) nepoužitelné. Typickým příkladem je diskrétní Fourierova transformace (DFT), která v obecném tvaru má asymptotickou složitost O(N²), proto je nevhodná pro transformaci vektorů větších délek. Existuje rychlá verze této transformace označovaná jako FFT (Fast Fourier Transform), která využívá skutečnosti, že pro délky vektorů N=K^M (kde K je určeno tzv. radixem transformace 2,4,8,... a M je přirozené číslo), lze tento problém zjednodušit na složitost O(N log N).

Příklad výpočetní složitosti

Počet prvků vstupních dat	Asymptotická složitost
Počet prvků vstupních dat	O(1)	O(N)	O(N log N)	O(N²)	O(N³)	O(2^N)
1	1	1	1	1	1	2
10	1	10	10	100	1000	1024
100	1	100	200	10000	1000000	10³⁰
1000	1	1000	3000	1000000	10⁹	10³⁰⁰
1000000	1	1000000	6000000	10¹²	10¹⁸	10³⁰⁰⁰

Pahýl

Tento článek je příliš stručný nebo postrádá důležité informace.
Pomozte Wikipedii tím, že jej vhodně rozšíříte. Nevkládejte však bez oprávnění cizí texty.

@@ Řádek 17: / Řádek 17: @@
 ==Snižování výpočetní složitosti algortimů==
-Snahou programátorů je asymptotickou složitost dostat alespoň na polynomiální úroveň, horší složitosti jsou v reálných aplikacích (tedy u vyšších N) nepoužitelné. Typickým příkladem je diskrétní [[Fourierova transformace]] (DFT), která v obecném tvaru má asymptotickou složitost O(N<sup>2</sup>), proto je nevhodná pro transformaci vektorů větších délek. Existuje rychlá verze této transformace označovaná jako [[FFT]] (''Fast Fourier Transform''), která využívá skutečnosti, že pro délky vektorů 2<sup>N</sup>, kde N je přirozené číslo, lze tento problém zjednodušit na složitost O(N log N).
+Snahou programátorů je asymptotickou složitost dostat alespoň na polynomiální úroveň, horší složitosti jsou v reálných aplikacích (tedy u vyšších N) nepoužitelné. Typickým příkladem je diskrétní [[Fourierova transformace]] (DFT), která v obecném tvaru má asymptotickou složitost O(N<sup>2</sup>), proto je nevhodná pro transformaci vektorů větších délek. Existuje rychlá verze této transformace označovaná jako [[FFT]] (''Fast Fourier Transform''), která využívá skutečnosti, že pro délky vektorů ''N=K<sup>M</sup>'' (kde ''K'' je určeno tzv. radixem transformace 2,4,8,... a ''M'' je přirozené číslo), lze tento problém zjednodušit na složitost O(N log N).
 ==Příklad výpočetní složitosti==