Lekce 1 - Úvod do teorie algoritmů

Tento článek je velmi důležitý, protože vysvětluje pojmy a skutečnosti, které se potom objevují ve všech algoritmech v této sekci. Rovnou říkám, že se budu snažit psát co nejstručněji a vše názorně vysvětlovat. Nečekejte tedy žádnou hromadu rovnic a čísel, někoho to možná zklame, ale určitě bude víc těch, které to potěší To však neznamená, že tu nebudeme hovořit o odborných věcech a termínech, i toho se dočkáte. Vysvětlíme si, co je to algoritmus a budeme se věnovat asymptotické časové složitosti a stabilitě. Já věřím, že vše se dá vysvětlit bez cizích slov a pomocí příkladů. Ve stejném duchu potom pokračuji i s dalšími algoritmy v této sekci. Pojďme tedy nyní porozumět tomu, jak počítače řeší dané úlohy a udělejme si úvod do problematiky algoritmizace - co v ní vůbec řešíme a co to stále počítáme.

Algoritmus

Když se bavíme o algoritmech, pojďme se tedy shodnout na tom, co ten algoritmus vůbec je. Jednoduše řečeno, algoritmus je návod k řešení nějakého problému. Když se na to podíváme z lidského pohledu, algoritmus by mohl být třeba návod, jak ráno vstát. I když to zní jednoduše, je to docela problém. Počítače jsou totiž stroje a ty nemyslí. Musíme tedy dopodrobna popsat všechny kroky algoritmu. Tím se dostáváme k první vlastnosti algoritmu - musí být elementární (skládat se z konečného počtu jednoduchých a snadno srozumitelných kroků, tedy příkazů). "Vstaň z postele" určitě není algoritmus. "Otevři oči, sundej peřinu, posaň se, dej nohy na zem a stoupni si" - to už zní docela podrobně a jednalo by se tedy o pravý algoritmus. My se však budeme pohybovat v IT, takže budeme řešit problémy jako seřaď prvky podle velikosti nebo vyhledej prvek podle jeho obsahu. To jsou totiž 2 základní úlohy, které počítače dělají nejčastěji a které je potřeba dokonale promýšlet a optimalizovat, aby trvaly co nejkratší dobu. Z dalších příkladů algoritmů mě napadá třeba vyřeš kvadratickou rovnici nebo vyřeš sudoku.

Co když budeme po počítači chtít, aby prohodil 2 čísla (tedy hodnoty 2 proměnných, pojmenovaných například a, b)? Jistě víte, že následující kód nebude fungovat:

a = b;
b = a;

Do proměnné a se uloží obsah proměnné b. Do proměnné b se potom uloží obsah proměnné a, ale ten je už b, takže je v obojím b. Musíme si tedy pomoci další proměnnou c:

c = a;
a = b;
b = c;

Nyní se obsahy proměnných a a b prohodily. Máme tu tedy první algoritmus na prohození dvou čísel. Všimněte si, že nelze říci "prohoď čísla". Musíme dokonale popsat co má program dělat pomocí soustavy příkazů.

Další důležitou vlastností algoritmu je, že musí být determinovaný. V každém kroku musí jít určit, zda proces skončil a pokud ne, lze jednoznačně říci, jak bude pokračovat. Algoritmus by měl také skončit se správným výsledkem a pokrýt tedy všechny vstupy. V našem jednoduchém případě by měl prohodit proměnné tehdy, zda bude a=10; b=20; a i tehdy, zda bude a=999; b=102. Hovoříme zde o tom, že algoritmus je obecný. Algoritmus musí být ještě konečný. Nemůže si dovolit se někde zacyklit, vždy musí skončit s konečným počtem kroků.

Časová složitost algoritmu a asymptotická notace

Časová složitost již podle názvu souvisí s dobou, po kterou daný algoritmus (tedy program) běží. Doba závisí na velikosti vstupu (třídění 10ti čísel bude jistě rychlejší, než třídění milionu čísel). Problém je v tom, že nemůžeme prohlásit: "Tomuto algoritmu to trvá 5 vteřin". To proto, že zcela jistě záleži na rychlosti počítače, na kterém program běží. Dále záleží např. na programovacím jazyce. Dokonce ani nemůžeme počítat instrukce procesoru, protože záleží na jeho architektuře. Místo času tedy počítáme příkazy, které počítač vykoná. Příkazem myslíme elementární operaci, jako je dosadit hodnotu nebo porovnat hodnotu (naplnit pole už ne, to je série dosazení). Potom také jednoduchá aritmetika. Avšak počítáme je v závislosti na vstupu.

Uveďme si algoritmus, který najde v poli minimum (tedy nejmenší prvek). Jistě víte, jak to uděláme: Budeme dělat, že je minimum první prvek a projedeme pole od začátku do konce. Pokud nalezneme něco menšího, prohlásíme to za nové minimum a pokračujeme dále. Na konci budeme mít minimální prvek. Pole musíme celé projet, pokud bude mít n prvků, musíme n krát porovnat uložené minimum s daným prvkem, n krát zvýšit proměnnou cyklu a několikrát za nové minimum dosadit. Dejme tomu, že v průměrném případě to uděláme 3n krát (tedy např. 30 operací pro pole velikosti 10). Časová složitost bude O(3n). A teď pozor, O(3n) je to samé, jako O(n). Proč? Protože nás zajímá kvalita algoritmu a konstanty nejsou podstatné. Definice asymptotické časové složitosti je velmi podobná definici limity. Ukažme si na příkladu, jak se pomocí ní dají porovnat 2 algoritmy.

Mějme algoritmus na seřazení pole čísel s časovou složitostí O(n²). Bude to například selection sort, který ve stručnosti nalezne vždy minimum v čase O(n) a to vloží na začátek pole. Potom najde další minimum ze zbylých prvků a "vloží" ho za předchozí minimum. Toto udělá také n krát, tedy výsledná časová složitost je O(n * n) = O(n²).

Mějme potom druhý, úplně hloupý algoritmus, který bude zkoušet všechny permutace čísel tak dlouho, dokud pole nebude sežazené. Permutací bude jistě O(n!), další operace pro jednoduchost zanedbáme, už takhle je složitost dost vysoká .

Nyní mějme naopak QuickSort, který zde pro jednoduchost vysvětlovat nebudu, ale dokáže setřidit pole s časovou složitostí O(n log n).

Pro názornost si ještě přidáme algoritmus s čas. složitostí O(n) a to i přesto, že se tak dobře třídící problém zvládnout nedá.

Přeci jen si tentokrát změřme čas, jak dlouho budou algoritmy třídit pole různých velikostí na jednom, stejně rychlém počítači. Budeme předpokládat, že 1 operace trvá 1ms:

Dejme tomu, že počítač měl frekvenci procesoru 3GHz. Co když ho zrychlíme? Ty špatné algoritmy přece půjdou potom rychleji, ne? No, nepůjdou. Zde právě vidíme tu kvalitu, přestože algoritmus se složitostí O(n) po 10ti násobném zrychlení počítače zvládne opravdu 10x více prvků, ale o těch dalších to říci nemůžeme. Zde zcela jistě nebude přímá úměra, zrychlení je pouze konstanta a když funkce roste moc rychle, je konstanta naprosto zanedbatelná. Podívejme se, jak by to vypadalo, kdybychom počítač zrychlili 10x, 100x a dokonce 1000x:

Dejme tomu, že třídíme 15 prvků (tedy podle předchozí tabulky třídíme 0,15 sekundy). Podívejme se, kolik toho za tuto dobu stihneme setřídit u ostatních algoritmů a jak si zrychlením pomůžeme:

hodnoty jsou zaokrouhlené

Vidíte, že když zrychlíme počítač 1000krát na takt 3 000 GHz, stejně si u složitosti O(n!) pomůžeme jen o pouhé 4 prvky. Kvalita algoritmu je špatná a zrychlení stroje není řešení. Musíme se poohlédnout po jiném algoritmu s lepší časovou složitostí.

Co jsme si odnesli? Že časová složitost rozděluje algoritmy do určitých kvalitativních kategorií. A je úplně jedno, jestli nějaký algoritmus potom milionkrát zrychlíme, protože se stejně nikdy nedostaneme z oné kategorie a vždy bude existovat takový počet prvků, od kterého bude algoritmus z jiné kategorie rychlejší. Jinými slovy algoritmus co třídí čísla v O(n log n) spuštěný na stařičké 486ce bude třeba od pole velikosti 1000 a více vždy rychlejší, než třídící algoritmus se složitostí O(n²), spuštěný na moderním stojádrovém serveru. Zrychlení handicap algoritmu na chvíli skryje, ale s rostoucím vstupem se vždy ztratí, pro dostatečně velká čísla se konstanta stane naprosto bezvýznamnou. (zasvěcení nyní poznali, že jsem odříkal definici limity

Symbol velké O se nazývá "velké O notace" nebo "Omikron notace". Znamená, že složitost daného algoritmu je asymptoticky menší nebo rovna výrazu v závorce. Udává tedy, jakou "třídu časové složitosti" algoritmus nikdy nepřekročí. Můžete se také setkat se symboly velké Omega (větší nebo rovno) a také s malými ekvivalenty omegy a omikronu, které symbolizují ostrou nerovnost. Konečně velké Fí je asymptoticky rovno.

Další vlastnosti algoritmů

Stabilita

O stabilním algoritmu hovoříme v případě, kdy zachovává předchozí pořadí takových prvků, které si jsou podle porovnávacího kritéria rovny. Pokud třídíme pole čísel, nemá to pro nás žádný užitek. Ale ve chvíli, kdy třídíme např. objekty nebo nějaké další kontejnerové struktury, může se nám to velmi hodit. Dejme tomu, že máme zaměstnance seřazené v poli podle abecedy. A my je chceme seřadit podle věku. Pokud řadící algoritmus není stabilní, může se nám stát, že dva stejně staří zaměstnanci (Adam a Zdeněk) budou v pořadí: Zdeněk, Adam. Stabilní algoritmus naopak v případě rovnosti zachová původní pořadí prvků, tedy Adam, Zdeněk. Zaměstnanci se stejným věkem tedy budou ještě seřazeni podle abecedy.

Na místě

Říkáme např., že třídíme na místě, pokud nepotřebujeme kromě vstupního pole žádnou dodatečnou paměť. Pokud ano, vzniká nebezpečí, zda budeme mít paměti vždy dostatek. Za tento paměťový handicap někdy můžeme dostat lepší časovou složitost nebo jiné výhody. V anglické literatuře se setkáte s termínem "In place".

To by bylo asi pro začátek vše, nyní si můžete bez problému procházet sbírku algoritmů, přítomnou na tomto serveru

U tabulek jsem se inspiroval materiály Unicorn College od profesora Ondřeje Kučery.

V příští lekci, Výpočet časové složitosti algoritmu, se naučíme spočítat časovou složitost určitého algoritmu.