Úvod do teorie algoritmů

Algoritmy Ú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ělit bez cízí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 algoritmlů 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 studenty 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.


 

  Aktivity (1)

Článek pro vás napsal David Čápka
Avatar
Autor pracuje jako softwarový architekt a pedagog na projektu ITnetwork.cz (a jeho zahraničních verzích). Velmi si váží svobody podnikání v naší zemi a věří, že když se člověk neštítí práce, tak dokáže úplně cokoli.
Unicorn College Autor se informační technologie naučil na Unicorn College - prestižní soukromé vysoké škole IT a ekonomie.

Jak se ti líbí článek?
Celkem (22 hlasů) :
4.681824.681824.681824.681824.68182


 


Miniatura
Všechny články v sekci
Česká encyklopedie algoritmů
Miniatura
Následující článek
Třídící/řadící algoritmy

 

 

Komentáře
Zobrazit starší komentáře (18)

Avatar
Martin Dráb
Redaktor
Avatar
Martin Dráb:

Přesně tak. Navíc také záleží, jak je daná implementace algoritmu optimalizovaná. Pak jsou ty konstanty (skryté O-notací) zase jiné.

Například pokud počítáš Levensteinovu vzdálenost dvou 32KB řetězců (tzn. počet operací přidej/uber/změň znak, který je třeba provést, aby se jeden z řetězců stal druhým), klasická implementace poběží třeba 1.7 sekundu, ale po použití vektorových instrukcí se můžeš dostat i na hodnoty 6x nižší.

Odpovědět 3.4.2015 13:12
2 + 2 = 5 for extremely large values of 2
Avatar
bem.jiri12
Člen
Avatar
bem.jiri12:

Výborná teorie o algoritmech, musel jsem se k této lekci vrátit a stála zato. Díky :)

 
Odpovědět 1.6.2015 22:15
Avatar
Jaroslav Polívka:

Dovedli byste nastínit nebo odkázat na algoritmus? Jak byste řešili? Máme kartézskou soustavu souřadnic, a v něm jeden obdélník, úkolem je vylosovat randomem souřadnice pro nový obdélník, avšak nesmí se vylosovat souřadnice toho obdélníka, který už tam je, ani souřadnice, které by do tohoto obdélníka zasahovali. Random se smí zavolat pouze 1x.

Odpovědět 6. března 20:15
Velice často si věci žijí svým životem
Avatar
Lukas C#
Redaktor
Avatar
Odpovídá na Jaroslav Polívka
Lukas C#:

Co bere ta funkce Random za parametry?

 
Odpovědět 6. března 20:47
Avatar
Odpovídá na Lukas C#
Jaroslav Polívka:

Napsal sem trochu nepřesně, bude se volat samozřejmě dvakrát, protože jednou vezme jako parametr celé číslo souřadnice x a podruhé jako souřadnici y. Nesmí se ale stát, že se vylosuje pozice toho obdélníku, který už tam je, nebo pozice, která by do tohoto obdélníku zasahovala. Oba obdélníky mají konstantní velikost.

Odpovědět 6. března 21:02
Velice často si věci žijí svým životem
Avatar
Jan Bajer
Člen
Avatar
Jan Bajer:

Dejme tomu, že třídíme 15 prvků (tedy podle předchozí tabulky třídíme 0,15 sekundy).

Nemělo by tam být 0,015 sekundy? :)

Odpovědět 9. června 13:06
Svět není takový, jak ho vnímáme, ale jak ho tvoříme.
Avatar
krepsy3
Redaktor
Avatar
krepsy3:

Já myslel, že když se napíše pouze "log", je považováno za základ e = 2,727272...
Tedy "přirozený logaritmus".

Odpovědět 6. srpna 9:30
Programátor je stroj k převodu kávy na kód.
Avatar
Lukas C#
Redaktor
Avatar
Odpovídá na krepsy3
Lukas C#:

To by bylo "ln". V případě "log" je základ 10.

 
Odpovědět  +1 6. srpna 10:25
Avatar
coells
Redaktor
Avatar
Odpovídá na krepsy3
coells:

To záleží na kontextu a oblasti.

V matematické analýze se log obvykle uvažuje o základu 10.
V analýze algoritmů se log obvykle uvažuje o základu 2.
A obecně se log pro změnu uvažuje o základu e, pokud v kontextu můžeme zanedbávat konstanty.

 
Odpovědět  +2 6. srpna 11:07
Avatar
krepsy3
Redaktor
Avatar
Odpovědět 6. srpna 11:37
Programátor je stroj k převodu kávy na kód.
Děláme co je v našich silách, aby byly zdejší diskuze co nejkvalitnější. Proto do nich také mohou přispívat pouze registrovaní členové. Pro zapojení do diskuze se přihlas. Pokud ještě nemáš účet, zaregistruj se, je to zdarma.

Zobrazeno 10 zpráv z 28. Zobrazit vše