Nahoru
 

Jak se určuje efektivita algoritmu

V současné době kvetoucí techniky, plné složitých programů i obrovských objemů dat, se musíme snažit programovat efektivní algoritmy. Mohou to být algoritmy na cokoliv, například vyhledávání v databázi, nalezení nejkratší cesty z místa A do místa B nebo výpočet čísla „Pí“. Jak však určíme efektivitu nějakého algoritmu? Můžeme vůbec porovnávat dva algoritmy a říci, který je efektivnější?

Představme si, že dostaneme do ruky dva programy a máme za úkol určit, který je efektivnější. Jak bychom takový problém řešili? Podle mě první věc, co by každému prolétla hlavou, by bylo změření času. Nejrychlejší program vyhrál. To je však extrémně zavádějící. Může se stát, že první program spoléhá na rychlejší paměť nežli výpočetní sílu a druhý přesně naopak. Jiné počítače vám poskytnou zcela protichůdné výsledky.

Jednotka pro „efektivitu“

Z předchozího příkladu vyplívá zřejmá věc. Algoritmy nemůžeme měřit dle času ani jiné fyzikální jednotky. Musíme býti více teoretičtí. Z článku „Co je to vlastně programování“ již víme, že program není nic jiného, nežli převzetí vstupu (dat) a „vyplivnutí“ výsledku. Pojďme se toho chytit a definujme si pojem asymptotická složitost.

Pojem asymptotická složitost nám pomocí matematické funkce říká, kolik operací musí algoritmus provést, na základě velikosti vstupu, aby zpracoval výstup. Neříká nám však úplně přesný počet operací, ale nejrychleji rostoucí matematickou funkci ze vzorce pro přesný výpočet operací. Na tu se přichází mnohokrát daleko snadněji nežli na přesný vzorec.

Složitost značíme pomocí „O“ spolu s přidruženou funkcí daného algoritmu, takže například O(1), O(log n), O(log log n), O(n), O(n2), O(n3).

Fraf funkcí: konstantní, logaritmická, lineární a kvadratická
Obrázek č. 1: Graf různých matematických funkcí (konstantní, logaritmická, lineární a kvadratická)

Nyní jsem pravděpodobně odradil všechny čtenáře, ale nebojte, není to tak složité. Ukažme si nějaké názorné příklady:

Algoritmus, který přijme libovolný počet položek, ale provede vždy jednu operaci, je konstantní: O(1). Nezáleží tedy na velikosti vstupu.

Algoritmus, který přijme vstup s deseti položkami a zpracuje je pomocí deseti operací, je lineární: O(n). Přesněji řečeno, pokud přijme „n“ položek, provede „n“ operací.

Algoritmus, který přijme vstup se sto dvaceti osmi položkami a zpracuje je pomocí sedmi operací, je logaritmický: O(log n). Přesněji řečeno, pokud přijme „n“ položek, provede „log n“ operací (většinou se základem dva). Je nutno podotknout, že „log n“ je opravu velmi efektivní. Například, pokud je „n“ rovný miliardě, potom „log n“ o základu dva je zaokrouhleně třicet. To je znatelná redukce.

Algoritmus, který přijme vstup s deseti položkami a zpracuje je stem operací, je kvadratický: O(n2). Přesněji řečeno, pokud přijme „n“ položek, provede „n2“ operací.

Může se stát, že algoritmus přijme „n“ položek, ale proveden například „2n + log n“ operací. V takovém případě nás zajímá pouze ta „největší“, resp. nejrychleji rostoucí funkce, což je lineární O(n).

Jak moc se lepší asymptotická složitost vyplatí?

Aby bylo zřejmé, jak moc se vyplatí tyto znalosti mít, pojďme si do hloubky ukázat základní, denně používaný algoritmus vyhledávání a jeho denní použití.

Neefektivní vyhledávání: Mějme milión náhodných seřazených čísel a hledáme jedno z nich. Velice jednoduchý a často používaný způsob s asymptotickou složitostí O(n), tedy lineární, by byl porovnat námi hledané číslo s úplně každou položkou v naší množině čísel. Pokud najdeme shodu, pak výborně, našli jsme námi hledaný prvek. V nejhorším případě tedy vždy provedeme milión operací. To je hrozně moc.

Efektivnější vyhledávání: Mějme milión náhodných seřazených čísel a hledáme jedno z nich. Víme, že čísla jsou seřazené, proto se podíváme do poloviny této sady a řekneme si: „Je mnou hledané číslo větší nebo menší, než toto prostřední číslo“? Jednou jedinou operací jsme nyní vyloučili celých půl milionu prvků! Takto můžeme opakovat stále dokola, až nalezneme námi hledané číslo. Tento konkrétní algoritmus se jmenuje binární vyhledávání a má složitost O(log n). V nejhorším případě provedeme vždy pouhých 20 operací!

Nejefektivnější vyhledávání: Mějme milión náhodných seřazených čísel a hledáme jedno z nich. Můžeme využít způsobu hashovacích tabulek, kde podle konstantního hashovacího algoritmu vezmeme hledané číslo a rovnou vypočteme jeho pozici. Vyhledávání je tedy konstantní O(1) a provedeme vždy stejný počet operací. Jedná se však o komplikovanější záležitost a přináší spoustu problémů. Musíme si totiž napsat vlastní hashovací funkci, což nemusí být vždy snadné. Ba co více, pokud nenapíšeme dobrou hashovací funkci, skončíme u O(n), tedy neefektivního vyhledávání. To nám u velice efektivního binárního vyhledávání nebo vybalancovaného binárního stromu vůbec nehrozí. Ano, hashování je teoreticky nejrychlejší, ale velice problémové a podle mého názoru zbytečně složité.

Dle mého názoru je binární vyhledávání naprostý vítěz. Je jednoduché na pochopení i realizaci a v milionech prvků vyhledá pouze pomocí dvaceti porovnaní. Asymptotická složitost O(log n) je skutečně extrémně rychlá, oproti (bohužel) nejčastěji používané lineární. Podobné principy se užívají i v databázových systémech, kde jsou data uloženy v tzv. n-árních binárních stromech.

Abstraktní zobrazení kreativity
Obrázek č. 2: Při tvoření algoritmů přemýšleje netradičně

Jak jsme mohli vidět na příkladu, není ani tak složité přijít s extrémně rychlým algoritmem. Chce to pouze důvtip a nějaké zkušenosti. Pokud jste se zalekli nad matematickými funkcemi, nepanikařte. Stačí rychlé připomenutí pomocí Googlu a za chvíli budete programovat efektivní algoritmy jako opravdový profesionál.