Když Vy i Váš kamarád dostanete stejné zadání problému, tak nejspíš každý navrhnete jiný algoritmus. Někdy i Vás samotné napadne více řešení. Jak poznat, který algoritmus je lepší? Mohli byste navrhnout, že ten, který proběhne rychleji. A nebo to bude ten, který bude potřebovat méně paměti? A nebo oba algoritmy proběhnou tak rychle a spotřebují tak málo paměti, že vybereme ten, který má kratší a jednoduší zdrojový kód? Všechny odpovědi mohou být správné. Záleží, co chceme optimalizovat:

  • Rychlost výpočtu, tj. za jak dlouho program proběhne. Jak dlouho budeme muset čekat, než se dozvíme výsledek?
  • Paměťovou náročnost. Kolik paměti program zabere? Bude stačit paměť, kterou v počítači máme? Pokud program potřebuje více paměti, než je k dispozici, tak se chybějící paměť nahradí pamětí na pevném disku. Ta je výrazně pomalejší a proto se tím zpomalí výpočet.
  • Rychlost, za jak dlouho program napíšeme.Některé věci potřebujeme spočítat jen jednou. Potom nezáleží tolik na rychlosti výpočtu, jako na celkovém čase, než program napíšeme a než program proběhne. Je jedno, jestli program poběží 1s nebo 5min, protože jeho naprogramování nám zabere podstatně více času. 

    Do času, za jak dlouho program napíšeme, spadá i odladění chyb. A to někdy trvá hodně dlouho. V kratších a jednodušších algoritmech je menší šance, že uděláme chybu.

Dobrý programátor si nejprve promyslí, na které z těchto kritérií se chce zaměřit a podle toho vybere vhodný algoritmus.

První dvě kritéria nás přivádí ke dvěma důležitým pojmům — časové a prostorové složitosti. Zhruba řečeno, časová složitost říká, jak dlouho algoritmus poběží v závislosti na velikosti vstupních dat. Prostorová (paměťová) složitost říká, kolik paměti je potřeba k vykonání algoritmu v závislosti na velikosti vstupních dat.

Tyto dvě věci spolu úzce souvisí. Zrychlení výpočtu můžeme dosáhnout tím, že si něco předpočítáme. Příkladem může být program, který na vstupu dostane $n \in \{1,\dots, 50\}$, a má odpovědět jestli lze šachovnici velikosti $n\times n$ proskákat šachovým koněm tak, abychom každé políčko navštívili právě jednou. Všechny odpovědi si můžeme předpočítat a uložit do tabulky. Nejrychlejší program se jen podívá do tabulky a vrátí odpověď. Použitelnější příklad může být předpočítání si prvočísel.

Předpočítané věci si ale musíme někam uložit a to nám může zvýšit prostorovou složitost. Proto se často stává, že rychlejší algoritmy mají větší prostorovou složitost a naopak.1

Praktické porovnávání algoritmů

Porovnání algoritmů lze provádět teoreticky i prakticky. Teoreticky můžeme nalézt odhad na počet kroků algoritmu (tj. jeho rychlost) a na spotřebu paměti. Často už v teoretických odhadech dostaneme takové rozdíly, že nemá smysl algoritmy dále porovnávat. Ale pokud je algoritmus složitý, tak může být nalezení správných odhadů těžké. Nejlepší odhady, které umíme ukázat mohou být mnohokrát horší než reálné hodnoty. Také záleží na tom, na kterých datech/vstupech budeme algoritmy používat. Z lepší znalosti vstupních dat můžeme ukázat mnohem lepší odhady než pro obecná data. Proto je lepší brát odhady časových složitostí jen jako první a hrubé porovnání. Pro lepší porovnání algoritmů nám nezbude nic jiného, než oba algoritmy naprogramovat. Potom oba programy spustíme na používaných datech, změříme časy výpočtu a velikosti zabrané paměti, a naměřené údaje porovnáme.

Dokonce se může stát, že praktickým porovnáním algoritmů dostane opačný závěr než teoretickým porovnáním. Tedy že se algoritmus s teoreticky vysokou časovou složitostí může prakticky chovat lépe než algoritmus s teoreticky nízkou časovou složitostí.2

Praktickému porovnávání algoritmů se v tomto textu nebudeme příliš věnovat, ikdyž je to v praxi velmi důležité. Jenom poznamenejme, že je potřeba měřit rychlost na stejném počítači a také na stejných vstupních datech. Také dost záleží na tom, ve kterém programovacím jazyce a jak dobře je který algoritmus implementován. I elegantní algoritmus lze implementovat úplně neelegantně. Čas běhu programu je také značně závislý na hardwaru, na kterém program běží (například drobné zvětšení vstupních dat může výrazně zpomalit běh celého programu, protože se nám najednou data nevejdou do paměti a budou se muset ukládat na disk). Podobná je i závislost na operačním systému.

Pokud už máme dobře proměřené chování algoritmů (jejich časové složitosti) na různě velkých datech, tak je můžeme porovnat. Následující obrázek zachycuje grafy časové složitosti dvou programů v závisloti na velikosti vstupu $n$. Může se stát, že jeden algoritmus bude lepší pro menší data (například pro $n\leq 100$) a druhý pro větší data (pro $n>100$). Který algoritmus vybrat?

Oba. Nejlepšího výsledku dosáhneme kombinací obou algoritmů. Pro malá data použijeme první algoritmus a pro velká data ten druhý.

Poznámka: Výborným tréninkem praktického programování je programovací soutěž ACM. Na adrese http://uva.onlinejudge.org/ si ji můžete vyzkoušet online (řadu dalších serverů s podobnou službou vygooglíte při hledání dotazu “online judge”). Server obsahuje archiv úloh, které se už někdy objevily programovacích soutěžích.

Vyberete si úlohu a dostanete zadání, které obsahuje popis problému, formát vstupů a formát výstupů. Až napíšete program, který úlohu řeší, tak ho odešlete na server. Soudce na serveru posoudí, jestli vaše řešení vrací správné výsledky a také změří, jestli je dostatečně rychlé. Do pár vteřin vám oznámí výsledek. Pokud váš program běží déle, než je stanovený limit, tak se řešení odmítne a vy musíte přemýšlet, jak to naprogramovat lépe. Na tom se přesně naučíte prakticky srovnávat algoritmy na konkrétních vstupech (velikost vstupu stejně jako čísel na vstupu je u každé úlohy omezena konstantou ze zadání).

K tomu, abyste byli v soutěži dobří, potřebujete rychle analyzovat problém, vymyslet dostatečně dobré řešení a co nejrychleji ho naprogramovat a odladit.

Teoretické porovnávání algoritmů

K teoretickému porovnání dvou algoritmů (tj. aniž bychom oba algoritmy naprogramovali) stačí odhadnout počet kroků, které každý algoritmus udělá v závisloti na velikosti vstupu.

Jak to udělat si vysvětlíme v následující kapitole \ref{chapter_casova_slozitost} o časové složitosti.