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

Skočit na navigaci Skočit na vyhledávání
Přidáno 66 bajtů ,  před 14 lety
m
(kapitola Snižování výpočetní složitosti algortimů)
==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''N=K<sup>NM</sup>,'' (kde N''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==
788

editací

Navigační menu