Studijní materiál: Složitost algoritmů

Pod složitostí algoritmu rozumíme dobu prováděného algoritmu (časovou složitost) a rozsah použité operační paměti (prostorovou složitost). Složitost závisí na velikosti vstupních dat, proto ji můžeme popsat jako funkci T(n), kde číslo n udává velikost vstupních dat. Například T(n) = an + b, kde a, b jsou nějaké konstanty, je zápis lineární časové složitosti (složitost roste lineárně s rostoucí velikostí vstupů). Obvykle je pro odhad složitosti důležitý pouze typ funkční závislosti a nikoliv přesné hodnoty konstant - ty se zanedbávají.

Za efektivní algoritmy považujeme takové postupy, jejichž složitost je polynomiální (např. n127, nikoliv exponenciální 2n). Provádění exponenciálních algoritmů či dokonce algoritmů o složitosti T(n) = n! může, už jen při malém navýšení velikosti vstupních dat, trvat i mnoho tisíců a miliónů let. Čím je algoritmus složitější, tím menší je vliv navýšení výkonu procesoru při velké velikosti vstupu. Ani polynomiální algoritmy s velkým stupněm polynomu nebo s velkými vstupními daty nejsou příliš rychlé.

V zápisu T(n) = an + b je a multiplikativní konstanta, která v sobě zahrnuje počet operací ve strojovém kódu, který je třeba provést pro vyřešení jedné operace na úrovni vyššího programovacího jazyka. Aditivní konstanta b udává pouze konstantní nárůst složitosti nezávislý na velikosti vstupních dat. Velikost této konstanty závisí jen na daném počítačovém systému, který algoritmus provádí. Při značné velikosti vstupních dat (to je situace, která nás vzhledem k složitosti algoritmu zajímá, při malých vstupech je složitost všech algoritmů poměrně nízká a vyrovnaná) můžeme konstanty a a b zanedbat, protože vzhledem k velikosti n jsou nepatrné, a výsledná složitost T(n) tak závisí především na velikosti n - velikosti vstupních dat algoritmu. Vybereme-li ze všech konstant a závisejících na použitém kompilátoru, který překládá program, největší konstantu, kterou označíme c, platí T(n) ≤ cn pro všechna dostatečně velká n. Tuto skutečnost značíme T = O(n), čímž vyjadřujeme asymptotické chování funkce T. Z této úvahy vychází matematická definice pojmů horní a dolní odhad složitosti algoritmu a složitost v průměrném případě (očekávaná složitost).