Složitost algoritmů
Abychom mohli porovnávat různé algoritmy řešící stejný problém, zavádí se pojem složitost algoritmu. Složitost je jinak řečeno náročnost algoritmu - čím menší složitost tím je algoritmus lepší.
Přičemž nás může zajímat složitost z pohledu času, či paměti. Jdo o tzv.:
- časová složitost - sleduje nároky algoritmu na čas. Jak dlouho trvá výpočet s tímto algoritmem? Dočkají se výsledku alespoň mé vnoučata?
- prostorová složitost - sleduje nároky algoritmu na paměť. Je schopen provést tento algoritmus můj počítač s omezenou pamětí?
Jelikož konkrétní čísla (čas, bity) se liší v závislosti vstupních datech, množství zpracovávaných dat a použitém programovacím jazyku, neudává se složitost čísly, nýbrž funkcí závislou na velikosti vstupních dat. Tato funkce se získá počítáním proběhlých instrukcí algoritmu sestaveném v univerzálním RAM stroji. A počítá se s nejhorším možným případem vstupu. To je důležité například u třídících algoritmů, kde hraje velkou roli to, jak moc už je vstupní pole setříděné (vstupuje-li do algoritmu už setříděná posloupnost čísel, algoritmus skončí okamžitě, zatímco s opačně seřazenými čísly se bude trápit dlouho. Proto při počítání složitosti cpeme do algoritmu ten nejhorší případ vstupu, při kterém se bude algoritmus trápit nejdéle.).
1. LOAD =0 //do pracovního registru (PR) ulož 0
2. STORE 1 // číslo v PR ([0]=0) ulož do registru [1]
3. LOAD =0 //do pracovního registru ulož nulu. PR = [0] = 0
4. STORE 2 // hodnotu PR ulož do registru 2. [2]=[0]
5. READ // načti vstup a posuň hlavu. [0]=IN
6. JZERO 13 // if([0]==0) jump(radek 13)
7. ADD 1 // K PR přičti registr [1]. [0]=[0]+[1]
8. STORE 1 // PR ulož do registru [1]. [1]=[0]
9. LOAD 2 // [0]=[2]
10. ADD =1 // [0]=[0]+1
11. STORE 2 // [2]=[0]
12. JUMP 5 // bez na radek 5
13. LOAD 1 // [0]=[1]
14. DIV 2 // [0]=[0] / [2]
15. WRITE // vypis pracovni registr [0]
16. HALT // konec programu
Výpočet složitosti pro algoritmus popsány instrukcemi RAM stroje vpravo bude následující:
Prvních 6 instrukcí se provede vždy, stejně jako poslední 4 instrukce. To je celkem 10 instrukcí které se provedou vždy i pro velikost vstupu n=1. Instrukce 5 až 12 tvoří smyčku čítající 8 instrukcí, která je závislá na velikosti vstupu n a provede se n-krát. Touto úvahou získáme následující funkci:
f(n) = 6 + n*8 + 4 = 8n + 10
Asymptotický odhad složitosi
Asymptonický odhada složitosti je další zobecnění složitosti algoritmu. Výpočet přesné funkce složitosti je pro komplikovanější algoritmy příliš náročný a navíc zbytečný. Pro představu o náročnosti algoritmu nám stačí vědět jak rychle funkce roste.
U předchozího příkladu nás tedy nezajímá kolik přesně instrukci se provedlo vně či vně cyklu, důležité je že funkce roste lineárně. Jak moc je lineární funkce nakloněná či zvednutá, není podstatné, protože každá kvadratická funkce ji nakonec předběhne. Tedy kvadratická složitost se při dostatečně velkém vstupu, stane vždy horší.
V souvislosti s asymptotickými odhady složitosti se používjí tyto zapisy:
• f ∈ O(g) . . . . f roste nejvýše tak rychle jako g = f je asymptoticky ohraničena funkcí g shora
• f ∈ o(g) . . . . f roste (striktně) pomaleji než g = f je asymptoticky ohraničena funkcí g shora ostře
• f ∈ Θ(g) . . . . f roste stejně rychle jako g
• f ∈ Ω(g) . . . . f roste rychleji než g = f je asymptoticky ohraničena funkcí g zdola
• f ∈ ω(g) . . . . f je asymptoticky ohraničena funkcí g zdola ostře
Pokud takto "zaokrouhlíme" a zjednoduším funkci složitosti, mluvíme pak o složitosti podle typu funkce.
• f(n) ∈ Θ(log n) . . . . logaritmická funkce (složitost)
• f(n) ∈ Θ(n) . . . . lineární funkce (složitost)
• f(n) ∈ Θ(n2) . . . . kvadratická funkce (složitost)
• f(n) ∈ O(nc) pro nějaké c > 0 . . . . polynomiální
• f(n) ∈ Θ(cn) pro nějaké c > 1 . . . . exponenciální
Jak je vidět na obrázku logaritmická složitost patří mez nejlepší, zatímco exponenciální, či faktorialová složitost je pro algoritmy zpracovávající větší vstupy neúnosná.
Problémy pro které existuje algoritmus s polynomiální složitosti se považují za prakticky zvládnutelné problémy.