Algoritmy: složitost

4.5. 2006 Vebloud Algoritmy

Jak známo, jsou programy rychlé a pomalejší, stejn? tak je to s algoritmy. Jak ale poznám, zda je mnou použitý algoritmus rychlý? Který z algoritm? ?ešících stejný problém je rychlejší, tím pádem lepší?

Existují minimáln? dva p?ístupy k ur?ení složitosti, respektive náro?nosti algoritm?. Absolutní složitost a asymptotická složitost. Ty se pak dále d?lí na pam??ovou náro?nost, procesorovou náro?nost atd. Asymptotická složitost slouží k porovnávání výkonnosti algoritm? z hlediska jejich principu a absolutní složitost slouží jak k porovnávání algoritm? jak z hlediska principielního, tak i jejich implementace.

Algoritmus a jeho implementace jsou rozdílné v?ci. Teoreticky m?že být algoritmus výkonný, ale pokud k jeho implementaci nepoužijeme správné metody a techniky, m?žeme celý jeho potenciál ztratit a zplodit pomalé tím pádem nefunk?ní monstrum.

Ne vždy je ale možno ur?it p?esnou složitost algoritmu, nebo složitost algoritmu nezávisí jenom na velikosti, nebo množství dat, ale p?ímo na jejich hodnotách. Tudíž se používá n?kolik zna?ení a notací, které jsou shodné jak pro asymptotickou, tak absolutní složitost.

• Ο(f_(n)) – Omikron notace (?asto se ?íká „velký O notace“, kdo by se zabýval ?e?tinou) – Horní odhad aneb horší už to nebude, ?asové nároky algoritmu nikdy neporostou rychleji než f_(n).
• Θ(f_(n)) – Theta notace – pr?m?rný odhad aneb n?jak tak to bude, ale m?že být lépe. Ale i h??.
• Ω(f_(n)) – Omega notace – Dolní odhad aneb lepší už to nebude

Typickým p?íkladem algoritmu se složitostí, která závisí na vstupních datech je algoritmus ?azení QuickSort jehož asymptotická složitost je O(eⁿ), což je šílené, ale taktéž Ω(log(n)), což je moc hezké, ale platí i Θ(n*log(n)).

Absolutní složitost:

Absolutní složitost je množství elementárních oparní, které se p?i vykonávání algoritmu provedou. Pro zjednodušení se uvažují elementární operace nad daty a pro ješt? v?tší zjednodušení se za elementární operaci bere každé porovnání. N?kdy se bere jako elementární operace také p?i?azení hodnoty prom?nné.

Ur?ení absolutní složitosti není vždy možné, protože na spoustu v?cí se používají knihovny a produkty t?etích stran, kde nemáme pon?tí o implementaci.

Asymptotická složitost:

Asymptotická složitost algoritmu vyjad?uje, jak rostou jeho nároky na výpo?etní výkon respektive ?as v závislosti na množství nebo velikosti vstupních dat, p?ípadn? oboje. Tyto dva parametry neznamenají totéž, nap?íklad p?i výpo?tu funkce faktoriál, nebo Ackermanovy funkce se množství vstupních dat nem?ní, vstupními daty je jedno, respektive dv? ?ísla, ale jejich velikost je velice d?ležitá.

Po?ítá se naprosto stejn? jako absolutní, ale vzhledem k tomu, že nás zajímá pouze závislost složitosti na množství vstupních dat, nepo?ítá každé porovnání a operace, nýbrž jenom tzv. asymptotická funkce. Tu dostaneme tak, že odstraníme multiplikativní (násobící) a aditivní (p?i?ítající) konstanty a necháme ve výsledku pouze funkci množství vstupních dat.

Asymptotická složitost je jediný zp?sob jak porovnávat algoritmy z hlediska principu, protože velikost aditivních a multiplikativních konstant závisí na podmínkách implementace algoritmu, použitém programovacím jazyce, zkušenosti programátora atd.

Není nic názorn?jšího než p?íklad, takže si ukážeme, jak to vlastn? vypadá na n?jaké klasické úloze.

T?eba procházení matice a provedení n?jaké operace konstantní složitosti nad každým prvkem matice o rozm?rech n x n (dvourozm?rné pole). Je pot?eba provést n2 p?echod? mezi prvky pole a n2 operací nad prvkem. Z toho je absolutní složitost Θ(n2 * p?echod + n2 * operace), z ?ehož vyplívá, že asymptotická složitost tohoto algoritmu je Θ(n2), nebo? p?i ur?ování asymptotické složitosti nás nezajímají multiplikativní a aditivní konstanty.