Algoritmická účinnost

Algoritmická efektivita je měřítkem toho, jak dobře algoritmus plní svůj daný úkol ve vztahu k využití zdrojů. Efektivní algoritmus vykonává maximální množství práce s využitím minimálního množství zdrojů, jako je čas, úložiště, paměť nebo energie. Algoritmickou účinnost lze měřit z hlediska časové a prostorové složitosti. V informatice je pojem efektivního algoritmu často přirovnáván k „nejlepšímu“ nebo „optimálnímu“ algoritmu.

Časová složitost je měřítkem toho, jak dlouho algoritmu trvá dokončení svého úkolu vzhledem k velikosti jeho vstupu. Algoritmus s časovou složitostí O(n) znamená, že jeho dokončení trvá lineárně dlouho, kde n je velikost vstupu. Algoritmus s časovou složitostí O(n^2) potřebuje kvadratické množství času na výpočet.

Prostorová složitost je mírou množství paměti, kterou algoritmus spotřebovává. Paměťová kritéria pro prostorovou složitost zahrnují celkovou prostorovou složitost (celková paměť použitá na konci běhu algoritmu), složitost pracovního prostoru (maximální paměť použitá v jakémkoli daném období běhu algoritmu) a pomocnou prostorovou složitost (prostor požadovaný algoritmem pro jeho špatné fungování). Podobně jako časová složitost je i prostorová složitost vyjádřena v notaci velkého O.

Nejúčinnější algoritmy jsou ty, které nejlépe využívají prostor a čas vyhrazený pro každý úkol. To znamená, že algoritmus s nízkou časovou a prostorovou složitostí překoná pro daný úkol algoritmus s vysokou časovou a prostorovou složitostí. Algoritmická efektivita je důležitým faktorem při hodnocení toho, jak dobře bude program nebo aplikace fungovat.