analýza algoritmov

analýza algoritmov — špeciálna disciplína informatiky zaoberajúca sa skúmaním takých vlastností algoritmov, ako je správnosť, množstvo času potrebného na vykonanie výpočtových krokov pri výpočte, množstvo pamäte potrebnej na vykonanie výpočtu, opisná jednoduchosť alebo optimálnosť. Pri analýze správnosti vzhľadom na danú vstupno-výstupnú špecifikáciu je základnou metódou formálne dokazovanie. Pri analýze množstva času i pamäte (analýza časovej, resp. pamäťovej zložitosti) sa abstrahuje od počítača i od konkrétnych vstupných údajov. Analýza sa vykonáva pre zvolený zjednodušený model počítača, pričom sa hľadá závislosť množstva času, resp. pamäte, od rozsahu vstupných údajov. Najčastejšie sa analyzuje príslušná závislosť pre najhorší možný prípad alebo pre priemerný prípad vzhľadom na možné hodnoty vstupných údajov. Optimálnosť algoritmu sa hodnotí vzhľadom na časovú, resp. pamäťovú zložitosť úlohy, t. j. vychádza sa z určenia dolného ohraničenia zložitosti ľubovoľného algoritmu, ktorý by riešil špecifikovanú úlohu. Pri špeciálnej triede algoritmov možno analyzovať aj ďalšie vlastnosti (napr. pri paralelných algoritmoch sa skúma aj zložitosť vzhľadom na počet procesorov).