Analýza algoritmu určuje požadované prostředky na jeho vykonání.
Prostředky mohou být čas potřebný na výpočet, paměť pro uložení dat, šířka komunikačního pásma pro přenos dat ap.
Nejčastěji nás zajímá čas výpočtu algoritmu. Důvodem je, kromě psychologického aspektu neochoty čekat na výsledky výpočtu příliš dlouho, skutečnost, že v mnoha aplikacích program musí poskytovat výsledky do nějakého času. Příkladem může být výpočet předpovědi počasí. Pokud z dostatečného počtu (možná velice velkého) dnešních měření meteorologických dat umíme vypočítat „přesnou“ předpověď na další den za tři dny, získáme výsledky, které jsou pro účel předpovědi již nepoužitelné.
Řešení otázky kolik času potřebujeme na vykonání programu by mohlo dát měření času trvání výpočtu na počítači. Obecně se s tímto postupem nemůžeme spokojit. Důvodů je několik.
V případě měření času výpočtu programu na počítači, tento bude záviset nejenom na vykonávaném programu, ale také na prostředí, které ho vykonává. Sem patří především rychlost procesoru. Dále, i na stejně rychlých počítačích můžeme získat různé výsledky použijeme-li různé překladače, či interprety. Pokud některé prostředky, například disk, jsou sdílené více programy, které jsou vykonávané současně, čas výpočtu bude záviset na chování ostatních programů. Čas výpočtu navíc může značně záviset na vstupních datech a také tomu tak často je. Prosté měření času výpočtu nám nedává dostatečnou informaci o tom jak dobrý je program z pohledu časové náročnosti. Navíc, zřejmě rozhodujícím faktorem pro rychlost výpočtu bude algoritmus implementovaný programem. V případě měření času, nehodnotíme časovou náročnost algoritmu přímo, ale současně jeho implementací v programovacím jazyce, která může být pro tentýž použitý algoritmus i počítač lepší nebo horší.
Musíme tedy čas výpočtu algoritmu vyjádřit tak, aby jsme mohli srovnávat časovou náročnost různých algoritmů a to bez ohledu na faktory uvedené výše.
Výpočet algoritmů budeme uvažovat na „standardních počítačích“ s jedním procesorem s obvyklou množinou instrukcí a zobrazením dat, jak jsme uvedli v první kapitole. Příkazy algoritmu vedou k vykonávaní operací nad daty. Operace realizované různými instrukcemi procesoru obecně netrvají stejně dlouho. Například operace násobení je typicky značně delší než operace sčítání. Tvání každé instrukce můžeme vyjádřit počtem elementárních kroků konstatní délky potřebných na její vykonání, čímž zohledníme různé doby vykonání instrukcí. Čas výpočtu algoritmu pro danou velikost vstupu potom budeme vyjadřovat počtem vykonaných elementárních kroků. Pro vykonání určité operace, možná složené z několika instrukcí, označíme počet elementárních kroků potřebných na její vykonání coperace. Je-li vykonána n-násobně, přispěje k času vykonání algoritmu počtem kroků n coperace.
Čas výpočtu obecně roste s velikostí vstupu. Velikost vstupu je obvykle počet zpracovávaných položek, např. počet prvků, které máme seřadit, velikost matice ap. Někdy může být velikost problému charakterizována, jak uvidíme, více hodnotami. Na druhé straně, například pro algoritmus, který rozhodne je-li zadané číslo prvočíslo, čas výpočtu bude záviset na velikosti zadaného čísla. Mírou velikosti tedy není počet položek, ale musíme kvantifikovat velikost vstupu podle velikosti zadaného čísla, v tomto případě například počtem jeho bitů v binární reprezentaci, tedy log2 x, kde x je zadané číslo.
Dále uvedeným způsobem vyjádříme čas výpočtu několika algoritmů jako funkce velikosti vstupu.
V následujícím příkazu if se příkaz provede, bude-li mít podmínka vyjádřena booleovským výrazem hodnotu true.
if (booleovský výraz)
příkaz;
Obecně, například obsahuje-li booleovský výraz hodně proměnných a závorek, nemusí být na první pohled zřejmé je-li to vůbec možné.
V matematické logice se odpovídající problém nazývá splnitelnost booleovských formulí.
Nechť v našem případě booleovský výraz pozůstává z n proměnných logického typu v1, v2, …, vn, m logických operátorů not, and, … a závorek. Podmínka v příkazu if je splnitelná, existuje-li přirazení hodnot true a false proměnným v1, v2, …, vn takové, že její hodnota je true. Například podmínka
(x && !y) && (!y && !z)
je splněna přiřazením následujících hodnot proměnným
x = true; y=false; z =false;
Naopak podmínka
(x && !y) && (!x && z)
není splnitelná.
Problém je tedy otázka: Je daná podmínka splnitelná? Následující algoritmus řeší problém splnitelnosti.
Pro každé možné přiřazení hodnot true a false proměnným v1, v2, …, vn vyhodnoť podmínku .
Jaký je čas výpočtu uvedeného algoritmu pro zjištění splnitelnosti podmínky? Jestliže přiřazení hodnoty proměnné trvá čas ch a čas každé logické operace čas co , potom vyhodnocení podmínky v závislosti na počtu proměnných n a počtu operátorů m trvá
T(n,m) = n ch + m co
Počet různých přiřazení dvou hodnot n prvkům je 2n a čas výpočtu algoritmu je
T(n,m) = 2n(n ch + m co)
a vidíme, že čas roste exponenciálně s počtem proměnných ve výrazu.
Algoritmus násobní dvou čtvercových matic a a b v jazyce Java je na obr.
.
Pokud pro účel pochopení času vykonání vnořených cyklů zanedbáme času výpočtu v hlavičkách příkazů cyklu for, můžeme čas výpočtu vyjádřit ve tvaru
n-krát vnější cyklus (
n-krát cyklus pro j ( cnulování +
n-krát vnitřní cyklus ( csčítání + cnásobení )))
a čas výpočtu v závislosti na velikosti matice je
T(n)=n2(cnulování + n( csčítání + cnásobení ))=
n3( csčítání + cnásobení ) + n2cnulování = an3 + bn2
kde a a b jsou kladné konstanty.
Vidíme, že máme-li vnořené cykly, přičemž každý z nich se má vykonat n-krát, počet opakování v nich obsažených výpočtů bude n, n2, n3, ..., a roste s hloubkou vnoření. Celková doba výpočtu pak bude dána jejich součtem, tedy obecně polynomem stupně k, kde k je počet vnořených cyklů.
Na příkladě algoritmu řazení vkládáním, kterým jsem zabývali v článku 2.2, si ukážeme, že počet opakování cyklu může být různý pro různé vstupy stejné velikosti. Doba výpočtu algoritmu potom nebude záviset jenom na velikosti vstupu, ale také na jeho konkrétní hodnotě.
Na obr.
je v komentářích algoritmu řazení vkládáním uveden počet opakování výpočtů v cyklech. V cyklu for se n-krát vykoná výpočet hlavičky, kterého čas vykonání označíme cfor a (n-1)-krát jeho tělo, ve kterém jsou tři příkazy přiřazení. Počet opakování vnitřního cyklu while je závislý na konkrétních hodnotách prvků posloupnosti. Obecně se vkládaný prvek a[i] může umístnit kamkoliv do posloupnosti předcházejících i prvků a označíme-li ki počet vykonání hlavičky cyklu while pro i=1,2, ..., n-1, je 1≤ ki ≤ i+1. V těle cyklu while se pak (ki - 1)-krát vykonají dva příkazy přiřazení. Čas výpočtu řazení vkládaním tedy je
Nejlepší případ pro nějakou velikost vstupu n je situace, když prvky posloupnosti budou seřazeny a v hlavičce cyklu while zjistíme, že jeho tělo se nevykoná ani jednou. Bude tedy ki =1 pro každé i=1,2, ..., n-1. Doba výpočtu řazení vkládáním v nejlepším případě potom je
T(n)=ncfor + 3(n-1)cpřiřazení + (n-1)cwhile
Obdobně jako v příkladě násobení matic, můžeme čas výpočtu řazení vkládáním vyjádřit ve tvaru an+b, kde a a b jsou konstanty, a je tedy lineární funkcí n.
Nejhorší případ z hlediska času výpočtu nastane, bude-li posloupnost seřazena obráceně. Pro tento případ, vkládaný prvek a[i] bude vložen vždycky na její začátek a tělo cyklu while se vykoná i-krát, tedy ki = i+1. Po dosazení do obecného vztahu čas výpočtu řazení vkládáním v nejhorším případě je
T(n)=ncfor + 3(n-1)*cpřiřazení + (n(n+1)/2-1)cwhile
+ (n(n-1)/2)cpřiřazení
Čas výpočtu v nejhorším případě tedy můžeme vyjádřit ve tvaru an2 + bn + c a je tedy kvadratickou funkcí n.
Vzhledem k tomu, že čas výpočtu algoritmu pro nejhorší případ je horním ohraničením času jeho výpočtu pro jakýkoliv vstup, je tento čas vhodným kritériem pro porovnávání algoritmů a je tak mírou časové složitosti algoritmů. Mezi nejhorším a nejlepším případem je celá řada vstupů a pro konkrétní algoritmus by jsme se mohli ptát jaký je jeho průměrný čas vykonání. Tady narážíme na problém definování průměrného případu. Pokud pro algoritmus řazení vkládáním jsou všechny permutace n prvků stejně pravděpodobné, potom můžeme říct, že průměrně bude vkládaný prvek vložen doprostřed předcházející posloupnosti prvků, tedy ki = i/2. Po dosazení do obecného vztahu pro výpočet času vykonání algoritmu řazení vkládáním opět dostaneme kvadratickou funkci. Tato situace, kdy nejhorší a průměrný případ mají zhruba stejnou složitost nastává poměrně často, což je další důvod pro používání času výpočtu algoritmu pro nejhorší případ jako míry časové složitosti algoritmu. Někdy ovšem používáme i čas výpočtu pro průměrný výpočet, pokud se to ukáže užitečné.
Položme si otázku co z výrazu an3 + bn2 dostatečně charakterizuje chování algoritmu, tedy míru růstu času výpočtu v závislosti na velikosti problému n?
Důležité je chování pro velká n, protože obvykle problémy malého rozsahu spočteme dostatečně rychle bez ohledu na algoritmus. Pro a=b=1 a n =1000 je celková hodnota uvedeného výrazu 1 001 000 000 a člen n2 přispívá podílem 0,1%. Pro a =1 a b = 1000 bude sice člen n3 v uvedeném výrazu pro n < 1000 menší než bn2 , ale pro n = 1 000 000 bude příspěvek členu bn2 opět 0,1%.
Člen n3 tedy intuitivně charakterizuje růst času výpočtu algoritmu v závislosti na velikosti vstupu.
Asymptotická složitost vyjadřuje limitní růst času výpočtu, když velikost problému neomezeně roste. Obvykle, až na vstupy malé velikosti, algoritmus, který je asymptoticky efektivnější je pak lepší volbou.
Růst funkce můžeme vyjádřit pomocí Θ-zápisu.
Funkce g(n) = Θ(f(n)) existují-li kladné konstanty c1, c2 a n0 takové, že 0 ≤ c1f(n) ≤ g(n) ≤ c2f(n) pro všechna n ≥ n0.
Graficky je tento vztah znázorněn na obr.
. Vidíme, že až na konstantní koeficient pro všechna n ≥ n0 je funkce g(n) stejná jako f(n). Funkci f(n) nazýváme asymptoticky těsným omezením funkce g(n).
Růst času výpočtu algoritmu násobení matic jsme intuitivně navrhli charakterizovat členem n3. Ukažme, že čas výpočtu uvedeného algoritmu je Θ(n3).
Musíme tedy najít kladné konstanty c1, c2 a n0 tak, aby pro všechna n ≥ n0 bylo
c1 n3 ≤ an3 + bn2 ≤ c2 n3 a,b > 0
Vydělením n3
c1 ≤ a + b/n ≤ c2
Zvolíme-li c1 = a, c2 = a + b/ n0, pro libovolné kladné n0 je uvedená nerovnost splněna. Samozřejmě, existují i jiné volby konstant c1, c2 a n0, ale důležité je, že existuje aspoň jedna taková volba.
Obecně, pro libovolnou polynomiální funkci p(n) = adnd + … + a0, ad >0 platí p(n) = Θ(nd). Poznamenejme, že konstanta je polynomiální funkce stupně 0 a tedy pro konstantu je Θ(n0) = Θ(1).
Θ-zápis omezuje funkci shora i zdola. Pro omezení shora používáme O-zápis.
Funkce g(n) = O(f(n)), existují-li kladné konstanty c a n0 takové, že 0 ≤ g(n) ≤ cf(n) pro všechna n ≥ n0.
Graficky je tento vztah znázorněn na obr.
. Je-li tedy g(n) = Θ(f(n)) je také g(n) = O(f(n)). Protože an3 + bn2 = Θ(n3) pro a>0, je také an3 + bn2 = O(n3). Možná je překvapující, že an3 + bn2 je také O(n4), co můžeme ověřit zvolíme-li c = a + |b| a n0 = 1. Zápis g(n) = O(f(n)) znamená pouze tolik, že nějaký konstantní násobek funkce f(n) asymptoticky shora omezuje funkci g(n), přičemž neříkáme nic o tom jak je toto omezení těsné.
Protože O -zápis je horním omezením, použijeme-li ho pro čas výpočtu algoritmu pro nejhorší případ, získáme horní omezení času výpočtu pro jakýkoliv vstup. Omezení O(n2) pro nejhorší případ času výpočtu algoritmu řazení vkládáním je omezením pro každý vstup. Všimněme si, že i když nejhorší případ času výpočtu algoritmu řazení vkládáním je Θ(n2), neznamená to, že čas výpočtu je Θ(n2) pro každý vstup. Čas výpočtu algoritmu řazení vkládáním pro nejlepší případ je totiž Θ(n) .
Podobně jako O-zápis asymptoticky omezuje funkci shora, Ω-zápis ji asymptoticky omezuje zdola.
Funkce g(n) = Ω(f(n)), existují-li kladné konstanty c a n0 takové, že 0 ≤ cf(n) ≤ g(n) pro všechna n ≥ n0.
Graficky je tento vztah znázorněn na obr.
.
Z definice jednotlivých zápisů vyjadřujících růst funkce, plyne následující tvrzení.
Pro libovolné dvě funkce f(n) a g(n) je g(n) = Θ(f(n)) právě když g(n) = O(f(n)) a g(n) = Ω(f(n)).
Uvedené tvrzení používáme na odvození asymptoticky těsného omezení z jejího horního a dolního asymptotického omezení.
Protože Ω-zápis je dolním omezením, bude dolní omezení času výpočtu algoritmu pro nejlepší případ také dolním omezením času výpočtu pro každý vstup. Například pro vkládání řazením čas výpočtu pro nejlepší případ je Ω(n), je tedy Ω(n) pro každý vstup. Je však také správné tvrzení, že čas výpočtu řazení vkládáním pro nejhorší případ je Ω(n2), kde nemluvíme o libovolném vstupu, ale právě o vstupu pro nejhorší případ..
Nyní můžeme říct, že pro libovolný vstup je čas výpočtu řazení vkládáním omezen zdola Ω(n) a shora O(n2).
Bude-li čas výpočtu algoritmu omezen shora pro nejhorší případ a zdola pro nejlepší případ stejnou funkcí, bude tato funkce jeho asymptoticky těsným omezení. Možno dokázat následující tvrzení.
Čas výpočtu algoritmu je Θ(f(n)) právě když jeho čas výpočtu pro nejhorší případ je O(f(n)) a pro nejlepší případ je Ω(f(n)).
Význam časové složitosti algoritmů si dokumentujeme na srovnání jejich dob výpočtů pro různé funkce velikosti vstupu. V tabulce na obr.
je uveden čas potřebný ke zpracování vstupních dat rozsahu n, jestliže počet operací, které je nutné provést, je dán funkcí f(n), přičemž provedení jedné operace trvá jednu mikrosekundu. Vidíme tedy, že nepolynomiální růst času výpočtu algoritmů neumožňuje reálné výpočty pro vstupy větších rozsahů.
Zkoumejme otázku jak nám pomůže pro zpracování rozsáhlých vstupů zvýšení rychlosti procesoru. Předpokládejme, že rychlost procesoru se zvýšila k-krát. Byl-li za čas t algoritmem s časem výpočtu f(n) na původním pomalejším procesoru vyřešen problém o velikosti a , tedy t = f(a), jak velký problém vyřešíme stejným algoritmem na počítači s rychlejším procesorem?
Ať rychlejší procesor spočítá za čas t problém se vstupem x. Původní procesor by potřeboval, protože je k-krát pomalejší, čas k-krát delší, tedy kt = f(x) a odtud x = f -1 (kt) = f -1 (k.f(a)).
Tabulka na obr.
ukazuje velikost x rozsahu zpracovatelných úloh v daném časovém limitu, které odpovídá zvětšení výpočetní rychlosti použitého počítače k =10, 100 a 1 000, přičemž původně bylo možno v daném časovém limitu zpracovat vstupní data o rozsahu n = a = 100. Ani 1000 násobné zvýšení rychlosti procesoru neumožní pro algoritmy s nepolynomiálním růstem času výpočtu významné zvětšení vstupu.
Algoritmy, jejichž čas výpočtu jsou asymptoticky omezeny polynomiální funkcí velikosti jejich vstupu se nazývají polynomiální a jsou prakticky použitelné. Samozřejmě, pokud by byl čas výpočtu algoritmu Θ(n100), nebude takový algoritmus pro vstupy velkého rozsahu použitelný, je však velice málo praktických problémů vyžadujících algoritmy s tak vysokým stupněm polynomu. Ukazuje se však, že máme-li pro problém polynomiální algoritmus, často se pro takový problém najde lepší polynomiální algoritmus. Navíc, skládaní polynomiálních algoritmů vede opět na polynomiální algoritmy. Voláme-li například v polynomiálním algoritmu konstantní počet metod implementujících polynomiální algoritmus, čas výpočtu složeného algoritmu je polynomiální.
Na druhé straně algoritmy, které jsou omezeny alespoň exponenciální funkcí velikosti jejich vstupu, se nazývají exponenciální, a pokud se nepoužívají pouze na vstupy malého rozsahu jsou prakticky nepoužitelné. Na tyto algoritmy vede tzv. metoda hrubé síly, kdy v algoritmu zkoumáme všechny možnosti. Například v algoritmu uvedeném pro řešení problému splnitelnosti booleovských formulí jsme zkoumali všechny přiřazení hodnot true a false n-tici proměnných co vedlo na 2n možností.