Analýza algoritmů

Analýza algoritmů je v matematické informatice určení rozsahu výpočetních prostředků potřebných k vykonání algoritmu. Jako primární kritéria náročnosti algoritmu se volí doba běhu a použitý paměťový prostor. Většina algoritmů je navržena tak, že mohou přijímat vstup o libovolné délce. Nákladnost (složitost) algoritmu je obvykle vyjádřena jako matematická funkce, která na základě délky vstupu určí časovou a paměťovou složitost výpočtu.

Obvykle se pojem „analýza algoritmů“ používá pro teoretickou analýzu chování algoritmu v závislosti na velikosti dat, viz asymptotická složitost. Jiná činnost je měření charakteristik konkrétního procesu, např. při profilování.

Analýza algoritmů je důležitá součást obecnější teorie složitosti, která poskytuje teoretické odhady potřebných zdrojů pro provedení jakéhokoli algoritmu, který řeší určitý výpočetní problém. Tyto odhady mohou poskytnout užitečná vodítka pro hledání efektivních algoritmů. Jestliže chceme algoritmy analyzovat, potřebujeme jazyk pro popis algoritmů (zdrojový kód nebo pseudokód) a výpočetní model. Výsledkem analýzy je obvykle funkce, která poskytuje odhad doby, po kterou se bude daný algoritmus vykonávat. Jejím parametrem (n) je velikost vstupních dat.

Doba běhu algoritmu v praxi závisí na mnoha faktorech. Je zřejmé, že výkonnější počítač při stejném vstupu provede daný algoritmus rychleji. Další úskalí spočívá v tom, jak se vlastně tento čas měří. Při opakování měření se může stát, že získáme rozdílné údaje doby běhu i pro zcela stejné vstupní hodnoty. Zvláště výrazný bývá tento rozdíl u malých časů. Výsledné hodnoty se proto počítají jako aritmetický průměr z několika měření. Praktické experimenty mají tato hlavní omezení:

• Experimenty je možné z časového hlediska provést jen s určitým souborem dat.
• Je těžké udělat porovnání dvou algoritmů – znamená to experimentovat za identických podmínek.
• Je nutné algoritmus implementovat a provést experimenty – vyjádřit v nějakém programovacím jazyce.

Analýza algoritmů je v praktické informatice velmi důležitá, protože použití neefektivního algoritmu může významně ovlivnit výkon a stabilitu systému. Například u aplikací, u kterých je důležitá rychlost, může dlouhé čekání na výsledek způsobit, že získaná data budou již zastaralá a zbytečná. Tento problém byl aktuální především v dobách, kdy počítače dosahovaly velmi omezených výkonů a strojový čas byl velmi drahý.

Reference

V tomto článku byl použit překlad textu z článku Analysis of algorithms na anglické Wikipedii.