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

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 spočítat se složitostí O(N log N).

 

 

==Amortizovaná časová složitost==