"Kazdy algoritmus ma svoju zlozitost"
Marko Berezovsky :)
Analyza zlozitosti algoritmu je vypocet, odhad, predpoklad poziadavkov na vypoctove prostriedky, ktore vykonanie algoritmu bude pozadovat v zavislosti na vstupnych datach. Zlozitosti vstupnych dat zavisi na konkretnom probleme.
Zlozitost problemu zavisi na vstupnych datach a preto vyjadrujeme najhorsiu, priemernu a najlepsiu verziu.
Asymptoticka zlozitost
Z praktickeho hladiska nas zaujima predovsetkym, ako sa bude algoritmus chovat pre (nekonecne) velke instancie problemu. Preto vacsinou vyjadrujeme rad rastu funkcie zlozitosti so zanedbanim prispevkov nizsich radov.
V asyptotickej zlozitosti nas teda zaujima, ako zavisi na velkosti vstupnych dat v limite, pokial velkost instancie problemu porastie nad vsetky medze. Je to teda zlozitost vyjadrena pre instancie problemu dostatocne velke, aby sa jasne prejavil rad rastu fukncie zlozitosti v zavislosti na velkosti vstupnych dat.
majme f(n) a g(n), n0 z N+ a c1, c2 z R+, tak potom pre kazde n >= n0, plati ze
c1.g(n) <= f(n) <= c2.g(n) - asymptoticky tesna medza - theta notace
f(n) <= c2.g(n) - asymptoticky horna medza - omikron notace
c1.g(n) <= f(n) - asymptoticky dolna medza - omega notace
V omega notaci f(n) sa ocitne kazda funkcia g(n), ktora je vzdy vacisa ako f(n), alebo po vynasobeni nejakou kladnou konstantou c, je uz vzdy vacsia ako f(n).
V omikron notaci f(n) sa ocitne kazda funkcia g(n), ktora je vzdy mensia ako f(n), alebo po vynasobeni nejakou kladnou konstantou c, je uz vzdy mensia ako f(n).
Vo fi notaci f(n) sa ocitne kazda funkcia g(n), ktora spada do omikron aj omega notace.
