Algoritmus se obvykle nedefinuje nijak příliš formálně: je to dostečně podrobný postup řešení nějaké úlohy, abychom jej mohli provést (nebo naprogramovat) bez hlubšího rozmýšlení. Zrovna tak je důležité, aby byla samotná úloha jasně popsaná. Například i obyčejné násobení čísel na papíře je ve všech potřebných ohledech algoritmem.
Není ani nijak formálně dané, jak by se měl algoritmus zapisovat. Vždy se nabízí možnost jej popsat lidsky, slovy. Pokud je algoritmus hodně složitý, může to být dokonce ta nejlepší možnost. Někdy to ale je nepohodlně zdlouhavý a málo přehledný způsob.
Jednodušší bývá vypomoci si pseudokódem, což je lidsky čitelný text formátovaný jako zdrojový kód. Oproti textu v odstavcích může být výrazně stručnější a je hned vidět, v jakém pořadí jsou kroky vykonávány. Opět máme obrovskou volnost ohledně formalit: nemusíme popisovat každý krok přesně jako pro počítač, stačí jej jen naznačit, aby člověk pochopil, o čem je řeč. Složitější algoritmy obvykle shrneme pseudokódem a potom podle potřeby dovysvětlíme obyčejným textem, proč a jak by měly fungovat.
V některých případech bývá elegantní použít flowchart čili vývojový diagram. To je pseudokód zakreslený do plochy: obdélníky znázorňujeme jednotlivé kroky výpočtu a šipkami vývoj, jak program kroky postupně vykonává. Rozhodovací struktury (a tedy i cykly) se zapisují kosočtvercem, ze kterého pro každou možnost vychází jedna popsaná šipka. Flowcharty dobře slouží například pro popis uživatelského rozhraní a popis programu na vyšší úrovni; pro popis složitých algoritmů většinou nejsou vhodné.
Když popíšeme algoritmus na řešení nějakého problému a ujstíme se, že doopravdy vede vždy ke správnému řešení, můžeme se zajímat o jeho nároky na hardware. Hlavně nás trápí, jestli algoritmus vyřeší naše problémy dřív, než zešedivíme. Když jsme optimisté a máme po ruce nějaká ukázková vstupní data, můžeme algoritmus naprogramovat, spustit a prostě změřit, jak dlouho běžel (a podívat se do zrcadla, jestli jsme zešedivěli). Někdy si ale nemůžeme dovolit takové podrobné měření; chtěli bychom nějaký jednoduchý vzoreček, kterým dobu běhu jednoduše odhadneme.
Nejčastěji odhadujeme čas běhu podle velikosti vstupních dat. Když na papíře násobíme dvě N-ciferná čísla, píšeme si jako mezivýsledky N řádků, každý o nejvýše N+1 cifrách; celkově tedy napíšeme N·(N+1) cifer mezivýsledků a výsledek samotný má ještě až 2·N cifer. To nám jako odhad stačí: řekneme, že ten algoritmus pro vstup velikosti N trvá případě něco jako N2, neboli kvadraticky dlouho. Mluvíme o složitosti v nejhorším případě; to, že 3000000·2000000 umíme spočítat rychle, nikoho moc nenadchne.
Jistě to není přesné: úplně jsme zapomněli, že mezivýsledky měly o N cifer víc a že nakonec ještě vypisujeme 2·N číslic výsledku. Tyhle členy do vzorečku nepíšeme proto, že mají nižší řád a prostě tedy na čas nemají takový vliv; můžeme je zapomenout. Jestli vám to připomíná zacházení s limitami, jste na správné cestě. Takovýhle odhad "trvá to něco jako vzoreček X" zapisujeme pomocí velkého písmene O stručně jako "algoritmus běží v čase O(vzoreček X)". Ještě se k tomu vrátíme na konci textu.
Paměťová složitost vyjadřuje množství paměti, kterou algoritmus potřebuje. Budeme s ní zacházet stejně hrubě jako s časovou složitostí: nezajímají nás megabajty, stačí odhad nějakým jednoduchým vzorečkem. A opět nás (naprosto nejčastěji) trápí paměťová složitost v nejhorším případě.
Pro připomenutí: dělitel čísla X je nějaké číslo Y, které dělí X beze zbytku: také můžeme říct, že X = Y·k pro nějaké přirozené číslo k. Největší společný dělitel je největší číslo, které je dělitelem obou zadaných.
Největší dělitel je jistě menší nebo roven než obě zadaná čísla (říkejme jim A, B), takže stačí vyzkoušet všechna taková čísla až do jedničky a vypsat první, které u obou dává nulový zbytek po dělení. Dělení jedničkou dává určitě výsledek beze zbytku, takže nejpozději tehdy algoritmus skončí. Zapsáno pseudokódem:
funkci nsd_hloupy(A, B) definujeme takto:
číslo M je menší z čísel A, B
číslo I cyklem projde všechna čísla od M do 1:
pokud A%I je 0 a zároveň B%I je 0, tak:
funkce navrací I
Tohle doopravdy funguje, takže se můžeme pustit do rozboru složitosti. Tentokrát nechceme vzoreček závislý na počtu čísel na vstupu (určitě budou vždycky dvě), ale raději přímo na jejich hodnotách. Největšího společného dělitele ale předem neznáme, v nejhorším případě tedy opravdu budeme muset vyzkoušet M různých hodnot a časová složitost je O(M) - kde M je menší z čísel A, B. Paměti potřebujeme všehovšudy čtyři proměnné, takže konstantní množství; píšeme, že paměťová složitost je O(1).
Není náhoda, že jsem funkci pojmenoval nsd_hloupy. Jiný, rychlejší algoritmus se obvykle označuje jménem Euklidův. Je také jednoduchý, ale musíme si všimnout jedné matematické zákonitosti: obě zadaná čísla od sebe můžeme vzájemně odečítat (dokud dávají kladné výsledky) a jejich největší společný dělitel se tím nezmění. Můžete si to zkusit matematicky dokázat, z předchozího vzorečku X =Y·k to jde snadno.
Řekněme si například, že A je menší než B. Můžeme tedy opakovat příkaz B = B - A pořád, dokud to dává kladný výsledek, tedy dokud je pořád A menší než B. Pokud se rovnají, máme hotovo: obě jsou navzájem svými největšími společnými děliteli. Pokud vyjde B menší než A, čísla prohodíme a pokračujeme znovu. Protože celou dobu jen odečítáme, výsledek je správný a stačí ověřit, že algoritmus někdy skončí.
Nejdřív si ale všimneme ještě jedné věci. Když odečítáme A od B, provedeme nejvýše B/A kroků a na konci bude hodnota B rovna zbytku po dělení číslem A. Můžeme si tedy ušetřit práci, nic neodečítat a rovnou dělit se zbytkem. To vše zapsáno pseudokódem:
funkci nsd_euklides(A, B) definujeme takto:
čísla A, B podle potřeby prohodí tak, aby A bylo menší (nebo rovno) B
pokud je A rovno 0:
navrací B
jinak:
navrací nsd_euklides(B%A, A)
Co jsme tím získali? Algoritmus teď nepoběží v čase lineárním, ale v O(log(M)). Mimochodem, nejdéle výpočet trvá, když jsou A, B dvě po sobě jdoucí Fibonacciho čísla. Důkaz není těžký - stačí projít běh algoritmu obráceně, od výsledku k zadání. Abychom čísla využili co nejlépe, výsledek by měl být 1 a druhé číslo je tedy 0. Potom v každém kroku musíme přičíst (přinejmenším jednou) větší číslo k menšímu, z čehož vznikne právě Fibonacciho posloupnost. Ta roste exponenciálně, počet kroků je tedy logaritmus.
Jednodušší důkaz je pro odhad složitosti O(log(A+B)), to také platí. Stačí postupovat krok po kroku podle běhu algoritmu a rozebrat si případy, kdy 2·A<B a kdy 2·A>B; v obou případech platí, že součet poklesne na méně než 2/3. To opět přímo vede na logaritmus.
Měření doby běhu algoritmu podle hodnoty nějakého čísla na vstupu může být trochu zrádné. V tomhle případě nám to sloužilo dobře a nikdo nám v takovém rozhodnutí nemůže bránit, ale u jiných algoritmů by to vedlo k matoucím závěrům. Zvykem je v podobné situaci radši odhadovat dobu běhu podle počtu bitů dotyčných čísel; hodnota B-bitového čísla je pak řádově 2B. Euklidův algoritmus je z tohoto úhlu pohledu O(log(2B)), tedy lineární, zatímco původnímu hloupému algoritmu jsme přisoudili nepěknou exponenciální složitost O(2B). V takovém světle se jeví jako opravdu hloupý.
Umět důkazy k maturitě určitě nemusíte. Mohly by se vám hodit leda, jestli vám dělá potíže zbytek téhle otázky.
K vyjádření "složitost je něco jako funkce f(N)" jsme používali zápis O(f(N)). Intuitivně je dobré to tak chápat, ale má to také přesný matematický význam.
Odhadujeme například funkci vyjadřující, jak dlouho opravdu trvá výpočet pro nějaký vstup délky N; označme si ji t(N). Chceme ji odhadnout nějakou hezkou funkcí (obvykle to bývá právě nějaká mocnina N, někdy násobená logaritmem), kterou jsme si vymysleli a označíme ji f(N). Když píšeme "t(N) je O(f(N))", znamená to, že pro nějakou dost vysokou konstantu c bude platit t(N) < c·f(N). Tu konstantu si můžeme vymyslet libovolně a občas může být hodně vysoká, ale jak ji jednou zvolíme, musí nerovnost platit i pro N blížící se nekonečnu. Naopak, pokud to v několika nízkých hodnotách neplatí, můžeme nad nimi mávnout rukou (to je výhodné, protože logaritmus občas dává nulu a z té nám žádné c nic kloudného neudělá). Přehlížíme je podobným způsobem, jako když počítáme limitu posloupnosti.
Pokud vám tenhle popis nesedí, na Wikipedii najdete podrobnější rozbor.
Důležité je, že hodně různých funkcí můžeme zápisem s velkým O porovnávat navzájem. Především, platí O(1) < O(N) < O(N2) < ..., libovolně až do nekonečna. Mohli bychom do toho doplnit i neceločíselné mocniny. Logaritmus se do toho zamíchá trochu zvláštním způsobem; je více než O(1), ale menší než jakékoliv maličké O(N0,00..01). Naopak, exponenciální funkce jsou větší než libovolná mocnina N a platí také O(2N) < O(3N) < ... < O(N!)
Abyste si nestěžovali, že teorie je šedivá, tady jej máte vyvedený v růžové. Jako důležité značky flowchartů stačí znát kulaté obdélníky start/konec, kosočtverce pro rozhodování a obdélníky pro ostatní výpočty. Často se také používají rovnoběžníky pro vstup a výstup. Podrobnější seznam najdete na anglické Wikipeddi.