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

Skočit na navigaci Skočit na vyhledávání
Přidáno 518 bajtů ,  před 14 lety
kapitola Snižování výpočetní složitosti algortimů
m (kat Třídy složitosti)
(kapitola Snižování výpočetní složitosti algortimů)
* 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é.
 
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).
 
==Příklad výpočetní složitosti==
788

editací

Navigační menu