Analýza programů

Analýza programu se zabývá nároky programu na zdroje, tedy čas, paměť, šířka pásma... Máme-li problém, lze pro jeho řešení zpravidla použít více algoritmů, a každý algoritmus může mít několik implementací. Analýza programů se zabývá právě vztahem implementace řešení původního problému vzhledem k požadovanému zdroji.

Obsah 1 Časová náročnost 2 Asymptotická složitost 3 Očekávaná složitost 4 Klasifikace složitosí

[editovat] Časová náročnost

Nejčastěji nás zajímá časová náročnost programu. Analyzujeme, jakou dobu bude implementovanému algoritmu trvat výpočet. Tuto dobu ovlivňuje způsob implementace (počet nutně provedených operací) a velikost vstupních dat (počet prvků, které algoritmus zpracovává, případně jejich uspořádání). Definujeme elementární čas pro všechny operace c_operace a jejich skádáním počítáme celkový čas potřebný pro provedení algoritmu.

Příklad: Naplnění již alokovaného pole náhodnými čísly (c#)

for (int i = 0, i < pole.Length; i++)
{
  pole[i] = rand.Next();
}

• máme pole délky n = pole.Length:
• alokace proměnné trvá c_aloc
• operace přiřazení trvá c_přiřazení
• operace porovnání trvá c_porovnání
• operaci inkrementace lze definovat jako c_inkrement = c_přiřazení + c_součet
• řekněme, že generování náhodného čísla trvá konstantní čas c_rand

• Inicializace cyklu for: alokace + přiřazení = c_aloc + c_přiřazení
• Běh cyklu: porovnání (i < length) + přiřazení (do pole) + náh. číslo + inkrementace (i++) = c_porovnání + c_přiřazení + c_rand + c_inkrement
• Cyklus for proběkne n-krát, tedy: n * ( c_porovnání + c_přiřazení + c_rand + c_inkrement )
• Celkem: c_aloc + c_přiřazení + n * ( c_porovnání + c_přiřazení + c_rand + c_inkrement )

[editovat] Asymptotická složitost

Ve většině případů neznáme čas potřebný pro konstantní operace, ale víme, že je velmi malý. Dobu výpočtu předchozího příkladu můžeme tedy přepsat na a + n * b, kde a a b jsou doby, které mají určitou délku, která nás však přísliš nezajímá.

Více než doba výpočtu nás tedy zajímá počet operací, které je třeba vykonat (stejně budou operace na každém systému vykonávány jinou dobu (PC vs. mobilní telefon např.)). Složitostí programu myslíme právě počet operací potřebný pro výpočet vzhledem k počtu prvků na vstupu algoritmu, omezený shora a/nebo zdola. Tato složitost se pro libovolný počet prvků asymptoticky blíží k určité funkci. Nás zajímá, ke které. Rozlišujeme také složitost algoritmu a složitost problému (ta by měla patřit do otázky PPA1).

Theta notace Θ(f(x)) vyjadřuje A.S., omezenou složitostní funkcí c_1,2 * f(x) shora, resp zdola. Hledáme tedy 2 konstatnty, pro které je analyzovaná složitost omezena.

Tato notace říká, že algoritmus nebude asymptoticky složitější než c₁ * f(x), a nebude rychlejší než c₂ * f(x). To znamená, že problém lze řešit algoritmem, který nebude asymptoticky složitější než c₁ * f(x), ale zároveň nikdy nebude lepší než c₂ * f(x).

Omikron notace O(f(x)) vyjadřuje A.S. omezenou funkcí c * f(x) pouze shora. Jinými slovy, jde o maximální možnou složitost algoritmu. Jde o první podmínku theta notace.

Omega notace Ω(f(x)) vyjadřuje A.S. omezenou funkcí c * f(x) pouze zdola. Říká, že algoritmus pro alespoň jeden vstup bude této složitosti. Druhá podmínka theta notace.

Pokud platí omikron a omega notace pro stejnou f(x), mluvíme o theta notaci.

Konstanty v notaci zanedbáváme, jelikož vzhledem k většímu n nehrají roli. Sčítáním složitostí tedy nedochází k jejich zhoršení, jsou-li stejného řádu (např n² + n² = 2n² => n², 200 operací je asymptoticky stejné jako 100, ale n² + n³ => n³ , 100 * 100 operací je vzhledem k 100 * 100 * 100 zanedbatelné).

Předchozí příklad je tedy složitosti Θ(n) , jelikož je vždy lineární vzhledem k délce pole (netrvá kratší, ani delsí dobu/počet operací)

[editovat] Očekávaná složitost

Většina algoritmů je asymptoticky omezena pro extrémní případny na vstupu (např. Quicksort je Ω(n) (pole již seřazeno) a O(n2) (pole je seřazeno opačně)). Chování algoritmu má však očekávanou složitost, která nastává pro většinu případů (jak víme O(n logn) pro QuickSort). Využívá se také Theta/Omikron/Omega notací.

Je-li algoritmus závislý na vstupních datech (resp. na jejich uspořádání), a potřebujeme, aby složitost byla pokud možno vždy očekávaná, lze využít náhodného přeuspořádání dat na vstupu (za předpokladu, že je to možné - např. pro řazení ano, pro výpis znaků na obrazovku evidentně ne). Toto přeuspořádání může být konstatní složitosti (např 100x přeházíme vzájemně prvky pole s náhodnými indexy pokud je pole rozumné odpovídající délky), případně lineární, složitost algoritmu tedy neovlivňuje (za předpokladu, že algoritmus samotný není očekávané sublineární časové složitosti).

[editovat] Klasifikace složitosí

Polynomiální - složitost O(n * c) kde c je konstanta. Polynomiální algoritmy jsou použitelné. Ideální jsou algoritmy rychlejší (lineární, logaritmické,...), ne vždy je však možné takový algoritmus vymyslet.

Exponenciální - složitost O(cⁿ). Tyto algoritmy nejsou příliš dobré, a je vhodné se zamyslet a pokusit se vymyslet jiný, polynomiálně složitý algoritmus. Zpravidla algoritmy hrubé síly jsou této složitosti, jelikož procházejí všechny kombinace vstupu a hledají řešení. Pro malé n jsou však použitelné díky menší režii a přípravě, paměťovým nárokům atd.

Postupy výše lze aplikovat i na složitosti paměťové, šířky pásma, ...