Lekce 1 - Úvod do teorie algoritmů

Vítejte u první lekce kurzu o algoritmech. Algoritmy v dnešní moderní době jsou všude kolem nás a využíváme je denně. Řeší jak jednoduché, tak i ty nejtěžší úlohy.

V dnešním tutoriálu o teorii algoritmů si řekneme, co je to algoritmus, jaké má vlastnosti anebo co je časová složitost algoritmu nebo asymptotická notace. Uvedeme si i nějaké příklady algoritmů.

Algoritmus

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.

Vlastnosti algoritmů

Algoritmy jsou:

• elementární,
• determinované,
• obecné a konečné,
• stabilní,
• na místě.

Elementární algoritmus

Dostáváme se tedy k první vlastnosti algoritmu - musí být elementární.

Algoritmus se musí skládat z konečného počtu jednoduchých a snadno srozumitelných kroků, tedy příkazů.

Úloha "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ž dvě základní úlohy, které počítače dělají nejčastěji. A proto je potřeba dokonale promýšlet a optimalizovat, aby trvaly co nejkratší dobu. Dalšími praktickými příklady mohou být například vyřeš kvadratickou rovnici nebo vyřeš sudoku. 

Determinovaný algoritmus

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.

Obecný a konečný algoritmus

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 také konečný. Nemůže si dovolit se někde zacyklit, vždy musí skončit s konečným počtem kroků.

Stabilní algoritmus

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.

Algoritmus Na místě

Třídíme na místě tehdy, 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áme s termínem "In place".

Praktická ukázka

Chtějme po počítači, aby prohodil dvě čísla. Tedy hodnoty dvou proměnných, pojmenovaných například a, b). Jistě víme, ž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 & b prohodily. Máme tu tedy první algoritmus na prohození dvou čísel. Všimněme si, že nelze říci "prohoď čísla". Musíme dokonale popsat, co má program dělat pomocí soustavy příkazů.

Č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ží na rychlosti počítače, na kterém program běží.

Dále záleží například 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.

Algoritmus na vyhledání nejmenšího prvku

Uveďme si algoritmus, který najde v poli minimum (tedy nejmenší prvek). Jistě víme, 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říkladech, jak se pomocí ní dají porovnat dva algoritmy.

Časová složitost O(n²)

Mějme algoritmus na seřazení pole čísel s časovou složitostí O(n²). Bude to například selection sort (více v lekci 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²).

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ůžeme 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.

Časová složitost O(n!)

Mějme potom druhý, úplně hloupý algoritmus. Ten 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á

Časová složitost O(n log n)

Nyní mějme naopak QuickSort (více v lekci Quick sort), který dokáže setřídit pole s časovou složitostí O(n log n).

Časová složitost O(n)

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

Výsledky jednotlivých algoritmů

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 jedna operace trvá 1ms:

Prvků	O(n)	O(n log n)	O(n2)	O(n!)
10	0,01 sekundy	0,03 sekundy	0,1 sekundy	1 hodina
15	0,015 sekundy	0,06 sekundy	0,2 sekundy	41 let
100	0,1 sekundy	0,7 sekundy	10 sekund	nevyčíslitelné
1000	1 sekundu	10 sekund	půl hodiny	nevyčíslitelné

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ů, pak 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á.

Výsledky algoritmů při různé frekvenci CPU

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:

Frekvence CPU	O(n)	O(n log n)	O(n2)	O(n!)
3 GHz (bez zrychlení)	15 prvků	6 prvků	4 prvky	4 prvky
30 GHz	150 prvků	30	12 prvků	5 prvků
300 GHz	1500 prvků	200 prvků	40 prvků	6 prvků
3 000 GHz	15000 prvků	1400 prvků	120 prvků	8 prvků

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é čtyři 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í.

Závěr

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. 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.

V příští lekci, Výpočet časové složitosti algoritmů, se naučíme spočítat časovou složitost určitých algoritmů u stejného problému. Ukážeme si jejich správné a špatné využití a na závěr si je porovnáme.