Pojďte s námi programovat !

c++

Pro prázdninové dvojčíslo jsme pro vás připravili speciální vydání programátorského kurzu jazyka C++. Speciální je proto,
že vzniklo podle ohlasů vás, ctěných čtenářů. Možná to bude znít neuvěřitelně, ale většina čtenářských námětů nás prosila o pečlivější výklad efektivnosti a složitosti algoritmů, což jsou dvě úzce propojené vlastnosti algoritmů, které jsme charakterizovali v jedné z úvodních lekcí našeho kurzu. Ano, přiznáváme, je to malinko neobvyklé, poněvadž analýza složitosti algoritmů přece jenom poněkud vyčnívá z náplně základního kurzu programování. Nicméně nelenili jsme, a na následujících stránkách se můžete seznámit s výsledky naší práce.



Analýza složitosti algoritmů

Efektivnost algoritmů je velice úzce spojena s analýzou složitosti algoritmů. Složitost algoritmů je předmětem zkoumání teorie složitosti algoritmů, která je jednou z disciplin matematické analýzy. Nutno ovšem podotknout, že analýza složitosti a potažmo rovněž výkonnosti algoritmů je poměrně náročná, neboť využívá bohatý matematický aparát a předpokládá vysokou úroveň analytického myšlení. Analýza složitosti algoritmů je tedy spíše doménou matematiků a matematicky orientovaných informatiků než běžných programátorů. Analytický přístup ke složitosti algoritmů umožňuje nejenom zjistit výpočtový čas algoritmu, ale také poskytuje kvantifikovatelný přístup ke vzájemné komparaci algoritmů. To je prospěšné tehdy, když máme před sebou dva algoritmy a snažíme se dopátrat skutečnosti, který z nich je pro danou situaci efektivnějším řešením. Možná dospějeme k závěru, že nejlepší bude napsat dva programy, které budou tyto algoritmy implementovat, spustit je se stejnou sadou vstupních dat a prostě změřit dobu jejich běhu. Ano, tento přístup se jmenuje empirická analýza algoritmů a doopravdy existuje. Bohužel, empirická analýza se jeví jako užitečný nástroj pouze při testování algoritmů s „rozumnými“ výpočetními časy. Jestliže jeden program poskytne požadovanou odpověď za deset sekund a druhý za dvacet, okamžitě usoudíme, že první algoritmus vykonává svoji práci efektivněji. Ovšem co když bude provádění jednoho programu trvat den a druhého dva dny? Jak sami uznáte, na světě existuje spousta atraktivnějších činností, než sedět u počítače a čekat, dokud se zkoumané programy nevypořádají se svými úkoly. Je zřejmé, že pro analýzu algoritmů, jejichž exekuční doba se pohybuje ve vyšších řádech, je nutné zapojit do hry exaktní matematickou analýzu.

Časová složitost algoritmů se zpravidla posuzuje vzhledem k objemu vstupních dat. Pokud objem vstupních dat označíme proměnnou n, pak můžeme prohlásit toto: Časová složitost algoritmu T(n) je funkce, která říká, kolik elementárních operací (kroků) se uskuteční při řešení problému o rozsahu n. Podobně bychom mohli definovat rovněž paměťovou neboli prostorovou složitost algoritmu. Paměťová složitost algoritmu S(n) je funkce, která udává, kolik paměťových jednotek spotřebuje algoritmus při řešení problému o rozsahu n. V dalším pojednání se omezíme pouze na zkoumání časové složitosti algoritmů (paměťovou náročnost odložíme stranou, poněvadž ji můžeme pro potřeby tohoto programátorského kurzu zanedbat).

Velikost čili rozsah vstupních dat (n) je přesně vyjádřen počtem bitů, které lze použít k uchování dat. V praxi je však velikost vstupních dat většinou dána vágněji jako počet čísel určených ke zpracování, počet prvků pole, počet hran grafu nebo obecněji jako rozsah zpracovávaných položek. Krok algoritmu je elementární operace, kterou lze na počítači realizovat v konstantním čase. Krokem algoritmu může být jedna z aritmetických operací (jako je třeba sčítání, odečítání či násobení), porovnání dvou čísel, nebo přiřazení hodnot. Elementární operaci zvládne procesor počítače provést jednou, případně malým počtem základních instrukcí. Ve skutečnosti je docela složité vyčíslit přesný počet elementárních operací, které procesor realizuje při zpracování jistého algoritmu. Při analýze algoritmů se můžeme setkat s dvěma variantami časové složitosti: absolutní časová složitost a asymptotická časová složitost. Absolutní časová složitost se soustřeďuje na vyčíslení množství elementárních operací, které algoritmus během svého zpracování uskuteční. Podle počtu operací pak dovedeme spočítat exekuční dobu algoritmu. Ovšem pozor! Exekuční doba algoritmu se může na různých počítačích lišit. Analýza absolutní složitosti algoritmu totiž bere v potaz veškeré „postranní“ konstanty a multiplikátory, které se vážou k mnoha proměnlivým faktorům (jako třeba výkonnost procesoru počítače, na němž algoritmus běží, nebo optimalizační nastavení kompilátoru, jenž byl použit k stavbě programu implementujícího zkoumaný algoritmus).

Naštěstí kvantifikování finitního počtu elementárních operací není za běžných okolností pro analýzu časové složitosti algoritmů až natolik zásadní. Je to proto, že pro analytiky je mnohem důležitější zkoumání vztahu, jenž determinuje, jak se počet operací zvyšuje v souvislosti se vzrůstajícím objemem vstupních dat. Uvažujeme-li „velký“ rozsah vstupních dat, smíme ignorovat všechny konstanty, které výsledný výpočtový čas algoritmu ovlivňují. A to nás přivádí k asymptotické časové složitosti algoritmů.

Předpokládejme, že absolutní časovou složitost imaginárního algoritmu popisuje funkce:

T(n) = an2 + bn + c

kde a, b, c jsou konstanty, které jsou dané. Kdybychom chtěli, mohli bychom za konstanty pro lepší srozumitelnost dosadit konkrétní hodnoty, kupříkladu a = 12, b = 10 a c = 7 . Tak se funkce vyjadřující absolutní časovou složitost algoritmu mění následovně:

T(n) = 12n2 + 10n + 7

Budeme-li předpokládat, že jedna elementární operace bude provedena v konstantním čase v délce jedné mikrosekundy (1 µs), pak při vstupu
n = 100 získáme za stanovených podmínek tuto funkci:

T(100) = 12 × 1002 + 10 ×100 + 7
T(100) = 12 × 10000 + 1000 + 7
T(100) = 121007 ?s

Skutečnost, že jsme se dopracovali k hodnotě přibližně 121 tisíc mikrosekund, pro nás není až tak podstatná. Tím nejdůležitějším jevem, na který hodláme poukázat, je, že hodnotu funkce v dominantní míře určuje především kvadratický člen n2. Objevená skutečnost se projeví ještě výrazněji, když bude n = 1000.

T(1000) = 12 × 10002 + 10 ×1000 + 7
T(1000) = 12 × 1000000 + 10000 + 7
T(1000) = 12 × 10002 + 10 ×1000 + 7
T(1000) = 12010007 ?s

Zvětšíme-li vstupní sadu dat desetkrát, výsledná exekuční doba naroste o takřka stonásobek. Nyní jasně vidíme roli, kterou ve funkci hraje kvadratický člen.

O představené funkci proto můžeme říci následující: Funkce odpovídá algoritmu s kvadratickou časovou složitostí, neboť primárním parametrem, jenž ovlivňuje délku běhu algoritmu, je polynom druhého stupně n2. V závislosti na objemu vstupních dat bude exekuční doba algoritmu stoupat kvadraticky, což není zrovna přijatelné, protože když se hodnota parametru n zvýší n-krát, výpočtový čas algoritmu vzroste n2-krát. Kvadratický člen společně se svým koeficientem (konstantou a) má ze všech členů tvořící funkční předpis největší váhu. Přitom platí, že i pro malé hodnoty konstanty a (přičemž a>0) bude kvadratický člen hrát prim. Vztah mezi kvadratickým (an2), lineárním (bn) a absolutním členem (c) lze kvantifikovat i v podobě limity, jejíž hodnota bude konvergovat k nule:

bn + c
lim an2 = 0

Je to konec konců logické, neboť jmenovatel zlomku
bn + c
an2
bude růst daleko rychleji než čitatel. Hodnota podílu se tak bude čím dál tím více přibližovat k nule.

Budeme-li uvažovat o poměrně velkém rozsahu vstupních dat, můžeme si dovolit veškeré multiplikativní a aditivní konstanty z našich úvah vypustit. Je to proto, že jejich přispění se na celkové exekuční době algoritmu neodráží v nijak zásadní míře (nejdůležitější je řád polynomu). Abstrahování od konstant multiplikativního a aditivního charakteru je zjednodušení, které přichází při zkoumání asymptotické časové složitosti algoritmů jako na zavolanou. Kromě eliminace zmíněných konstant nám asymptotická časová složitost pomůže s klasifikací algoritmů do jednotlivých výkonnostních tříd. V neposlední řadě nám nabídne rovněž mechanizmus pro účinné srovnávání zkoumaných algoritmů.

Asymptotická časová složitost je nejčastěji reprezentována takzvanou O-notací neboli notací velké-O, pomocí níž je možné určit asymptotické horní omezení složitosti algoritmu.

Horní omezení je užitečné, poněvadž sděluje informaci, že časové nároky zkoumaného algoritmu již neporostou výše (tím pádem tedy reprezentuje nejhorší možnou výkonnost algoritmu). O-notace nám umožňuje vyjádřit asymptotické chování funkce T(n). Pro naši funkci T(n) = an2 + bn + c
proto můžeme pomocí O-notace zapsat, že T(n) ? O(n2) nebo též T(n) = O(n2).

O-notace je natolik významná, že si zaslouží pečlivou matematickou definici.

Definice O-notace

Ať f(n) a g(n) jsou dvě nezáporné funkce definované na množině přirozených čísel (N). Říkáme, že f(n) je velké O od funkce g(n) a zapisujeme f(n) = O(g(n)), nebo též f(n) ? O(g(n)), jestliže existuje přirozené číslo n0 a konstanta c > 0 takové, že pro každé n ?n0 platí f(n) ? c × g(n). Ve zkratce lze O-notaci definovat takto:

f(n) ? O(g(n)) ????c > 0, ??n0 > 0 : ?n ? n0 :
f(n) ? c × g(n)

Pokud je f(n) ? 0(g(n)), můžeme prohlásit, že řád funkce f(n) je menší nebo nanejvýš rovný řádu funkce g(n). 0(g(n)) proto slouží jako horní odhad složitosti funkce f(n). O naší funkci T(n) = an2 + bn + c tak povíme, že její asymptotická časová složitost je v O(n2). Méně formálně: můžeme identifikovat takovou kladnou konstantu c, že počínaje nějakým číslem n0 bude graf funkce f(n) ležet vždy „pod“ grafem funkce c ×g(n). Tuto situaci znázorňuje obrázek.

Pro informatiky je nejdůležitější O-notace, protože jim dává garanci horního odhadu asymptotické časové složitosti algoritmu. Pomaleji, než udává O-notace, algoritmus už nepoběží. Kromě O-notace, která slouží k vyjádření horní meze časové složitosti algoritmů, jsou však zajímavé také další odhady, a sice odhad dolní a průměrné složitosti. Pro asymptotické dolní ohraničení složitosti algoritmu se používá ?-notace (? je omega) a pro asymptotické průměrné ohraničení složitosti algoritmu se zase aplikuje ?-notace (? je théta).
Definice ?-notace

Ať f(n) a g(n) jsou dvě nezáporné funkce definované na množině přirozených čísel (N). Říkáme, že f(n) je ? od funkce g(n) a zapisujeme f(n) = ?(g(n)), nebo též f(n) ???(g(n)), jestliže existuje přirozené číslo n0 a konstanta c > 0 takové, že pro každé n ? n0 platí f(n) ? c× g(n).

Ve zkratce lze ? -notaci definovat takto:

f(n) ? ?(g(n)) ????c > 0, ??n0 > 0 : ?n ? n0 :
f(n) ? c × g(n)
Definice ?-notace

Ať f(n) a g(n) jsou dvě nezáporné funkce definované na množině přirozených čísel (N). Říkáme, že f(n) je ? od funkce g(n) a zapisujeme f(n) = ?(g(n)), nebo též f(n) ? ?(g(n)), právě tehdy, když platí:

f(n) ? ?(g(n)) ????c1, c2 > 0, ??n0> 0 :
?n ? n0 : c1 × g(n) ? f(n) ? c2 × g(n)

Při použití ?-notace se zkoumá asymptotické oboustranné omezení funkce f(n). Algoritmy je možné podle jejich asymptotické časové složitosti klasifikovat do tříd, z nichž nejběžnější jsou následující:
Asymptotická časová složitost algoritmů uvedených tříd je pomocí O-notace prakticky zobrazena v tabulce. Pro zjednodušení předpokládáme, že uskutečnění jedné elementární operace vyžaduje 1 mikrosekundu (µs) strojového času.

V tabulce jsou algoritmy seřazeny sestupně podle jejich stoupající asymptotické časové složitosti. Zcela nejrychlejší jsou algoritmy s konstantní časovou složitostí, poněvadž u těch je zaručeno, že jejich elementární operace budou provedeny v konstantním čase. Není proto podstatné, jak velká sada vstupních dat bude zpracována, algoritmus třídy O(1) bude realizovat svou práci stejně rychle. Příkladem algoritmu s konstantní složitostí je třeba indexování prvků v poli. Velice rychlé jsou rovněž algoritmy s lineární, logaritmickou a lineárně-logaritmickou časovou složitostí, neboť s vzrůstajícím objemem vstupních dat časové nároky algoritmů rostou pouze pozvolna. Algoritmy s polynomiální časovou složitostí, což jsou algoritmy tříd O(n2) a O(n3) , jsou sice v praxi ještě použitelné, ovšem jak si můžete povšimnout, jejich složitost se rapidně zvedá, zejména pro velké porce vstupních dat. Pokud je to jenom trochu možné, obloukem se snažíme vyhnout algoritmům s exponenciální (O(2n))a faktoriální časovou složitostí (O(n!)). Algoritmy zmíněných tříd jsou v pravém slova smyslu požírači výpočetních zdrojů procesoru a jejich složitost je v mnoha případech natolik ohromná, že jejich praktické uplatnění je téměř nulové. Pohled na porovnání algoritmů z hlediska jejich asymptotické časové náročnosti nabízí další obrázek.

Na obrázku je namalován terč se třemi zásahovými zónami, přičemž každé zóně bylo přisouzeno číselné označení. V oblasti s číslem 1 mají schůzku nejrychlejší algoritmy, tedy přesněji algoritmy s nejpříznivějším horním odhadem své časové náročnosti. Sem patří algoritmy s konstantní délkou, dále algoritmy s lineární, logaritmickou a lineárně--logaritmickou povahou. Zásahová zóna s číslem 2 sdružuje algoritmy s polynomiální časovou složitostí. Průběh těchto algoritmů není tak rychlý jako u algoritmických protějšků z první kategorie, ovšem stále se ještě jedná o prakticky využitelné algoritmy. Bohužel, toto tvrzení už nemůžeme vyslovit o algoritmech, jejichž spádová oblast je označena číslem 3. V tomto segmentu leží v praxi neaplikovatelné algoritmy s exponenciální a faktoriální časovou složitostí. Uděláte dobře, když si algoritmů tohoto formátu nebudete příliš všímat. Jaké ponaučení tedy z uvedeného plyne? Milí přátelé, snažte se mířit co možná nejvíce do středu terče. Přesný zásah se v teorii algoritmické složitosti počítá hned dvakrát! Po zjištění asymptotické časové složitosti algoritmů základních tříd se můžeme na věc podívat také z jiného pohledu. Můžeme se zeptat, s jakou maximální sadou vstupních dat dokáží algoritmy pracovat za předpokladu, že provedení jedné elementární operace trvá 1 milisekundu (ms). V další tabulce jsou shromážděné údaje, které charakterizují výkonnost algoritmů podle maximální možné datové propustnosti. Pro lepší názornost zkoumáme, s jak velkým rozsahem dat se dovedou algoritmy poprat během 1 sekundy, 1 minuty a 1 hodiny. Nejvíce operací s daty provedou v našem přehledu algoritmy s lineární časovou složitostí. Řádově nižší výkonnost prokazují algoritmy s lineárně-logaritmickou složitostí, které ve srovnání s lineárními algoritmy ztrácí více než 80?%. Na tomto místě bychom rádi poukázali na lišící se hodnoty, jež generují algoritmy pracující s dekadickým a binárním logaritmem. Zajímavé je, že největší disproporce lze pozorovat u hodnoty reprezentující množství zpracovaných dat za hodinu výpočtového času. Celkový počet datových operací se rapidně snižuje, když se do hry zapojí algoritmy s polynomiální a exponenciální časovou složitostí. Máme tedy před sebou další důkaz, s jehož pomocí lze s přehledem usvědčit tyto algoritmy jako vůbec nejpomalejší. Jako zcela udivující se může jevit fakt, že algoritmus s exponenciální složitostí třídy je schopen produkovat pouze 22 datových operací za hodinu výpočetní časové dávky. Grafické vyjádření srovnání maximální datové propustnosti představených algoritmů nabízí další graf.
8 0364/CZ o

Poznámka Všimněte si, že O-notace u algoritmů s logaritmickou a lineárně-logaritmickou časovou složitostí postrádají specifikaci logaritmického základu. Znamená to, že tyto třídy složitosti mohou pracovat s logaritmy o základu 10 (dekadické logaritmy), e (přirozené logaritmy), nebo také 2 (binární logaritmy). V teorii, která rozebírá složitost algoritmů (a v informatice obecně), mají důležité postavení binární logaritmy, tedy logaritmy se základem 2 a kladnou mantisou. Binární logaritmus má označení lg x, přičemž platí, že
lg x = log2 x . Binární algoritmy se liší od dekadických svým základem, což je patrné na první pohled. To, co už tak zřejmé asi není, je skutečnost, že jakýkoliv logaritmus se základem 10 lze přepsat jako podíl binárních logaritmů, asi takto:
log2 x
log10 x = log210
Zavedením dříve zmíněné symboliky se převod změní následovně:
lg x
log10 x = lg 10
Při analýze asymptotické časové složitosti algoritmů není zase natolik signifikantní skutečnost, zda používáme dekadický, přirozený nebo binární logaritmus. Jejich hodnoty se liší pouze o konstantu, takže ačkoliv nám budou vycházet různé výsledky, odchylka nebude tolik významná.
algoritmy s konstantní časovou složitostí:
O(1)

algoritmy s logaritmickou časovou
složitostí: O(log n)
algoritmy s lineární časovou složitostí: O(n)
algoritmy s lineárně-logaritmickou
časovou složitostí: O(n × log n)
algoritmy s kvadratickou časovou
složitostí: O(n2)
algoritmy s kubickou časovou složitostí:
O(n3)
algoritmy s exponenciální časovou
složitostí: O(2n)
algoritmy s faktoriální časovou složitostí:.
O(n!)