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(n2). 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(n2).
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:
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číslitené |
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ů, 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:
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é 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(n2), 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.