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

Snahou programátorů, ale i teoretiků, 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]]Rychlá (''Fourierova transformace|Fast Fourier Transform]]'' (FFT), 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).

Pro opravdu velká data jsou často i nelineární algoritmy příliš náročné. Viz [[Big data]]. Když nemáme vhodný algoritmus, poskytující přesné výsledky, tak použijeme jiný algoritmus a pak se musíme spokojit s přibližným řešením, pravděpodobně správným řešením, heuristickým řešením a pod. anebo vhodnými technikami zmenšit zpracovávaná data.

Běžné implementační až [[hacker]]ské triky obvykle zrychlí konkrétní složitost algoritmu, tj. sníži multiplikativní konstantu v asymptotické složitosti, ale nezmění asymptotickou složitost. Sem patří [[inline funkce]], rozvíjení těla cyklu a převedení rekurze na iteraci. Na druhé straně, dobrou zprávou je, že když takové optimalizace vynecháme, ignorujeme, nebo nemáme ve svém oblíbeném [[kompilátor]]u, tak to nezhorší asymptotickou složitost nezhorší. TedaTedy stačípomůže použítpoužítí výkonnějšívýkonnějšího hardwarehardwaru.