Analýza algoritmů

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání

Analýza algoritmů je v matematické informatice určení rozsahu prostředků potřebných k vykonání algoritmu. Jako primární kritéria pro analýzu algoritmů 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. Efektivita (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.

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 poskytují užitečná vodítka při hledání efektivních algoritmů.

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í.

Kritéria použitá při analýze[editovat | editovat zdroj]

Doba běhu algoritmu či operace na datových strukturách závisí na mnoha faktorech. Na první pohled je zřejmé, že výkonnější počítače při stejném vstupu provedou daný algoritmus rychleji než méně výkonné stroje. Další úskalí spočívá v tom, jak se vlastně tento čas měří a o čem tyto metody vypovídají. Při opakování měření se může stát, že získáme rozdílné údaje doby běhu i pro absolutně stejné vstupní hodnoty. Zvláště výrazný je tento rozdíl u malých časů. Výsledné hodnoty se proto počítají jako aritmetický průměr z několika měření. Čas tedy může kolísat pro vstup dané velikosti a není to tím, že bychom špatně či nedokonale měřili.

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.

Jestliže chceme algoritmy analyzovat, musíme mít nějaký jazyk pro popis algoritmů (zdrojový kód nebo pseudokód) a příslušné prostředky a techniky pro analýzu. Pro teoretickou analýzu se používají a porovnávají různé výpočetní modely.

Běhová analýza[editovat | editovat zdroj]

Běhová (run-time) analýza je druhem teoretické analýzy programových algoritmů, díky které lze odhadnout dobu, po kterou se budou dané algoritmy vykonávat na základě velikosti vstupních dat (obvykle označovaných jako parametr n). Tento postup je aplikován na složitější algoritmy, protože doba, po kterou mohou být vykonávány, se může pohybovat od několika sekund až po celé roky. Příkladem takového algoritmu je prolamování šifer.

Rychlosti algoritmů v závislosti na procesoru[editovat | editovat zdroj]

Protože algoritmy jsou platformně nezávislé, je důležitým faktorem ovliňujícím dobu provádění jednotlivých algoritmů architektura procesoru, na kterém je daný algoritmus analyzován. Dnes nejběžněji používané architektury procesorů jsou architektury RISC a CISC. Rozdíl mezi těmito architekturami jsou jejich instrukční sady, které se liší v počtu používaných instrukcí. Architektura RISC používá pouze základní instrukce na rozdíl od architektury CISC, která kromě základních instrukcí používá i velmi složité instrukce, které by však šly naprogramovat pomocí kombinace těch základních. Z logického hlediska jsou jednodušší instrukce vykonávány rychleji než ty složitější, proto i výsledné programy by měly být rychlejší.

Dalším faktorem je počet strojových cyklů na jeden instrukční cyklus. Strojový cyklus je jeden tik jádra procesoru, který synchronizuje činnost všech jeho částí, a jeden instrukční cyklus je doba, za kterou se provede jedna instrukce. Proto počet strojových cyklů na jeden instrukční cyklus je dalším faktorem ovlivňující výsledný čas provádění daného algoritmu. Čím méně strojových cyklů je na jeden instrukční cyklus tím je procesor rychlejší.

Rychlost algoritmu závisí na mnoha dalších věcech, např. na spolupráci s keší. I stejný algoritmus lze různě implementovat a následně má různé chování. Přizpůsobení algoritmu konkrétnímu procesoru (nebo typu procesoru) je možné. Obvykle, pro běžné programy, se nedělá a částečně se spoléhá na optimalizující kompilátor, že nízkoúrovňové optimalizace provede. A to nemluvím to tom, že některé kompilátory mají různé úrovně optimalizací.

Význam[editovat | editovat zdroj]

Analýza algoritmů je v praxi 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ů. Snahou bylo vytvořit co nejrychlejší algoritmus, aby byl co nejlépe využit strojový čas, který byl v té době velmi drahý.

Související články[editovat | editovat zdroj]

Reference[editovat | editovat zdroj]

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