Složitost algoritmu
Z CHWiki
Obsah |
[editovat] Motivace
Pokud řešíme nějaký problém, vyvstává otázka jaký použít algoritmus případně jakou použít datovou strukturu. Hlavními kritérii pro nás bude, jestli daný algoritmus řeší co potřebujeme, a jak rychle to zvládá. Vyvstává ale otázka, jak rychlost algoritmu určovat, jak zjistit, který algoritmus je rychlejší a tak podobně.
Nejjednodušší by bylo všechny dostupné algoritmy naprogramovat a potom se stopkami zjišťovat, jak dlouho poběží. Přístup je to zajímavý, ale neřeší co se stane, když kousků dat nebude deset, ale miliarda... A co teprva když to budu ladit na pentiu 100 a pak to pustím na 3GHz počítači. Jak se algoritmus zrychlí?
Protože otázek je velmi mnoho, nezbývá než je vyřešit!
[editovat] Zavedení symbolu O
Pozor přijde matematika!
Abysme měli co klasifikovat, budeme měřit, kolik se provede základních operací (porovnání, přiřazení, ...) na jednotku dat.
Pokud chci vědět, jestli se mi z hromady věcí některá jejich část vejde do batohu, mohu to zkusit dělat tak, že pro každou věc rozvětvím program - v jedné větvi ta věc bude, v jiné nebude. Je to řešení problému, je výhodné tím, že je jednoduché (přijít na to bylo snadné), ale má jeden háček. Když se zamyslíme nad tím co děláme, dojdeme k tomu, že doba běhu se nám u každé věci násobí dvěma. Takže čas T(n) pak bude 2×2×2×2×...×2 (n dvojek), takže T(n) = 2n. Tak to zkusíme pro dvě věci. Program ihned ukáže výsledek. Postupně budeme zvyšovat velikost dat.. třeba na 50. To není tak moc... A ejhle. Program asi nefunguje, spustí se, ale nic nevypisuje. Ale to jste na omylu, program běží a počítá. Jenom mu to bude trvat hoodně dlouho. Když vezmete v úvahu, že vesmír tu je jen asi 2100 vteřin, tak se není čemu divit. Pokud vím, že daný problém budu řešit jenom pro dvě až pět věcí, nemám problém. Pokud vím, že občas budu potřebovat vyřešit věcí sto až tisíc, ten algoritmus je zcela nepoužitelný a musím hledat jiný, lepší – rychlejší právě v tom smyslu, jakým se zabývá odvětví algoritmické složitosti.
Pro vypsání tabulky zápasů v turnaji každý s každým musím pro každý tým projet všechny ostatní. To znamená T(n) = n*(n-1) [pro n týmů]. Ve výsledku tedy T(n) = n*n - n. Pokud se nad tím zamyslíte, pro hodně velká n člen n*n výrazně ustřelí k velkým číslům a n mu nebude stačit. Skoro se na výsledku nebude podílet. Proto ho můžeme směle zanedbat. Takže zatím vidíme, že nám stačí brát v úvahu největší člen.
Proto se používá symbol O - takzvaná asymptotická složitost. Vyjadřuje řádově časovou složitost algoritmu. Neuvedu zde přesnou definici (je mimo rámec této wiki), ale jedná se v podstatě o odhad složitosti algoritmu shora. Pro problém týmů by pak složitost byla O(n²).
Teď by Vás asi napadlo, co kdybych generoval ty výsledky dvakrát, byla by složitost O(2 * n²)? Odpověď zní ne. Funkce x² a 2x² totiž roste řádově stejně rychle, proto je ta dvojka pohlcena symbolem O (pro přesnější zdůvodnění opět nahlédněte do definice O). (Ve škole se také učíte o kvadratických funkcích, a je to jak x², tak 2x².)
Takže abysme si to shrnuli - pro klasifikaci časové složitosti algoritmu se používá symbol O(), který určuje řádově odhad shora. To znamená, že dva algoritmy se stejným O() budou běžet zhruba stejně rychle.
Doba provádění f(n) operací (délka běhu algoritmu) pro vstupní data velikosti n za předpokladu že použitý hardware je schopen vykonat 1 milion operací za sekundu:
http://tutchek.igroup.cz/wiki/delka_behu.gif
Pozn: O(1) znamená konstantní rychlost - žádný asymptoticky lepší algoritmus nevymyslíte. Rychlost totiž nezáleží na velikosti dat, tzn to bude stejně rychlé na jedné položce, jako na milionu.
[editovat] Je O jediný symbol?
Není. I když je asi potkáte méně často, ještě v infromatickém světě létají symboly malé o(f(n)), velká omega: Ω(f(n)), malá omega: ω(f(n)) a théta: θ(f(n)).
- O(f(n)) - odhaduje funkci shora (tzn. určitě to není horší než to)
- o(f(n)) - odhaduje funkci ostře shora (tzn. určuje vždy minimálně o řád více)
- Ω(f(n)) - odhaduje funkci zespoda (tzn. je vždy menší nebo rovna)
- ω(f(n)) - odhaduje funkci ostře zespoda (tzn. je vždy minimálně o řád menší)
- θ(f(n)) - odhaduje funkci shora i zdola (tzn. je zhruba stejná)
Opět berte příměry s rezervou... těžko se definice s několika kvantifikátory a proměnnými shrnuje do jedné věty.
[editovat] A jak je to při upgradu počítače?
Většina lidí má zažitou myšlenku, že pokud počítač upgraduje desetkrát, vše poběží desetkrát rychleji. Do jaké míry je to pravda, se podíváme:
Růst rozsahu zpracovatelných úloh, tj. „zvládnutelné“ velikosti vstupních dat, díky zrychlení výpočtu (lepší hardware) za předpokladu, že na „stávajícím“ hardware lze řešit úlohy velikosti x:
http://tutchek.igroup.cz/wiki/zrychleni.gif
Z tohoto je vidět, že pokud by na pentiu 100MHz program na řešení problému batohu (viz výše) našel za rozumný čas uspořádání pro 50 položek, na počítači s procesorem 100Ghz by našel 59 položek. Není to super? (Tedy: asymptotická složitost ukazuje, že u algoritmu s exponenciální složitostí umožní tisícinásobné zvýšení dostupného výkonu zvětšení rozsahu řešitelného problému jenom o konstantu, nejenže nejsme schopni řešit tisíckrát složitější problém, ale jsme schopni řešit jenom o devět složitější problém.)
Z tohoto tedy vyplývá - pokud to půjde (např. batoh je tzv. NP-úplná úloha, tam se předpokládá, že rychleji než jak zde bylo popsáno to nepůjde) - snažte se o algoritmy s polynomiální složitostí (n, n2, n5, n.log(n), 1, ...), protože u těch jen šance, že výsledky uvidíte už vy a ne až vaše děti, jak by tomu bylo v případě algporitmů s exponenciální složitostí (2n, ...)
