Analýza algoritmů

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

Analýza algoritmu je v informatice postupné provádění algoritmu vedoucí k žádanému výsledku v konečném čase, kdy určujeme množství prostředků nutných k jeho vykonání. Jako primární kritéria pro analýzu algoritmů lze zvolit dobu běhu (running time) algoritmu a použitý paměťový prostor. Tato dvě kritéria jsou obvykle v určitém rozporu v tom smyslu, že při pokusu o konstrukci rychlejšího algoritmu je nutné zvýšit paměťové nároky.

V oblasti algoritmizace se jako procesor bere interpret, který provádí daný algoritmus. V informatice se proto slovo procesor stalo synonymem k elektronickému obvodu s vysokou mírou integrace. Ale procesorem může být i člověk, protože i ten vykonává různé algoritmy, například vaření jídel podle pevně daných receptů.

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

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 budou vykazovat rychlejší provedení algoritmu než méně výkonné počítače, při stejném vstupu. 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 nám může stát, že získáme rozdílné údaje doby běhu, pro absolutně stejné vstupní hodnoty. Zvláště problematická je tato skutečnost u malých časů. Výsledné hodnoty se proto získávají, 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. Také díky rozdílu hardwarové platformy, budou časy pro provedení algoritmu na výkonnějším počítači lepší a naopak. Experimenty však mají tři hlavní omezení a to:

  • 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ů (pseudokód) a příslušné prostředky a techniky pro analýzu.

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 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, kdy záleží jak na velikosti hledaného klíče tak na složitosti prolamované šifry.

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

Význam[editovat | editovat zdroj]

Analýza algoritmů je v praxi velmi důležitá, protože náhodné nebo neúmyslné použití neefektivního algoritmu při náhodném nebo neúmyslném programování 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 ještě nedosahovaly takový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.