1. diel - Úvod do teórie algoritmov

Tento článok je veľmi dôležitý, pretože vysvetľuje pojmy a skutočnosti, ktoré sa potom objavujú vo všetkých algoritmoch v tejto sekcii. Rovno hovorím, že sa budem snažiť písať čo najstručnejšie a všetko názorne vysvetľovať. Nečakajte teda žiadnu hromadu rovníc a čísel, niekoho to možno sklame, ale určite bude viac tých, ktoré to poteší To však neznamená, že tu nebudeme hovoriť o odborných veciach a termínoch, aj toho sa dočkáte. Vysvetlíme si, čo je to algoritmus a budeme sa venovať asymptotickej časovej zložitosti a stabilite. Ja verím, že všetko sa dá vysvělit bez cudzích slov a pomocou príkladov. V rovnakom duchu potom pokračujem aj s ďalšími algoritmy v tejto sekcii. Poďme teda teraz porozumieť tomu, ako počítače rieši danej úlohy a urobme si úvod do problematiky algoritmizácia - čo v nej vôbec riešime a čo to stále počítame.

Algoritmus

Keď sa bavíme o algoritmoch, poďme sa teda zhodnúť na tom, čo ten algoritmus vôbec je. Jednoducho povedané, algoritmus je návod na riešenie nejakého problému. Keď sa na to pozrieme z ľudského pohľadu, algoritmus by mohol byť napríklad návod, ako ráno vstať. Aj keď to znie jednoducho, je to celkom problém. Počítače sú totiž stroje a tie nemyslí. Musíme teda dopodrobna opísať všetky kroky algoritmu. Tým sa dostávame k prvej vlastnosti algoritmu - musí byť elementárne (skladať sa z konečného počtu jednoduchých a ľahko zrozumiteľných krokov, teda príkazov). "Vstaň z postele" určite nie je algoritmus. "Otvor oči, sundaj perinu, Posanje sa, daj nohy na zem a Postavte sa" - to už znie celkom podrobne a jednalo by sa teda o pravý algoritmus. My sa však budeme pohybovať v IT, takže budeme riešiť problémy ako zoraď prvky podľa veľkosti alebo vyhľadaj prvok podľa jeho obsahu. To sú totiž 2 základné úlohy, ktoré počítače robia najčastejšie a ktoré je potreba dokonale premyslieť a optimalizovať, aby trvali čo najkratšiu dobu. Z ďalších príkladov algoritmov ma napadá treba vyrieš kvadratickú rovnicu alebo vyrieš sudoku.

Čo keď budeme po počítači chcieť, aby prehodil 2 čísla (teda hodnoty 2 premenných, pomenovaných napríklad a, b)? Iste viete, že nasledujúci kód nebude fungovať:

a = b;
b = a;

Do premennej a sa uloží obsah premennej b. Do premennej b sa potom uloží obsah premenné a, ale ten je už b, takže je v oboch b. Musíme si teda pomôcť ďalšie premennú c:

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

Teraz sa obsahy premenných aab prehodili. Máme tu teda prvý algoritmus na prehodenie dvoch čísel. Všimnite si, že nemožno povedať "Prehoď čísla". Musíme dokonale popísať čo má program robiť pomocou sústavy príkazov.

Ďalšou dôležitou vlastnosťou algoritmu je, že musí byť determinovaný. V každom kroku musí ísť určiť, či proces skončil a ak nie, možno jednoznačne povedať, ako bude pokračovať. Algoritmus by mal tiež skončiť so správnym výsledkom a pokryť teda všetky vstupy. V našom jednoduchom prípade by mal prehodiť premenné vtedy, či bude a = 10; b = 20; ai vtedy, či bude a = 999; b = 102. Hovoríme tu o tom, že algoritmus je všeobecný. Algoritmus musí byť ešte konečný. Nemôže si dovoliť sa niekde zacykliť, vždy musí skončiť s konečným počtom krokov.

Časová zložitosť algoritmu a asymptotická notácie

Časová zložitosť už podľa názvu súvisí s dobou, počas ktorej daný algoritmus (teda program) beží. Doba závisí na veľkosti vstupu (triedenie 10tich čísiel bude iste rýchlejší, než triedenie milióna čísel). Problém je v tom, že nemôžeme vyhlásiť: "Tomuto algoritmu to trvá 5 sekúnd". To preto, že celkom iste záleži na rýchlosti počítača, na ktorom program beží. Ďalej záleží napr. Na programovacom jazyku. Dokonca ani nemôžeme počítať inštrukcie procesora, pretože záleží na jeho architektúre. Namiesto času teda počítame príkazy, ktoré počítač vykoná. Príkazom myslíme elementárne operáciu, ako je dosadiť hodnotu alebo porovnať hodnotu (naplniť pole už nie, to je séria dosadenie). Potom tiež jednoduchá aritmetika. Avšak počítame je v závislosti na vstupe.

Uveďme si algoritmus, ktorý nájde v poli minimum (teda najmenší prvok). Iste viete, ako to urobíme: Budeme robiť, že je minimum prvý prvok a prejdeme pole od začiatku do konca. Ak nájdeme niečo menšieho, prehlásime to za nové minimum a pokračujeme ďalej. Na konci budeme mať minimálnu prvok. Pole musíme celé prejsť, ak bude mať n prvkov, musíme n krát porovnať uloženej minimum s daným prvkom, n krát zvýšiť premennú cyklu a niekoľkokrát za nové minimum dosadiť. Dajme tomu, že v priemernom prípade to urobíme 3n krát (teda napr. 30 operácií pre pole veľkosti 10). Časová zložitosť bude O (3n). A teraz pozor, O (3n) je to isté, ako O (n). Prečo? Pretože nás zaujíma kvalita algoritmu a konštanty nie sú podstatné. Definícia asymptotickej časovej zložitosti je veľmi podobná definícii limity. Ukážme si na príklade, ako sa pomocou nej dajú porovnať 2 algoritmy.

Majme algoritmus na zoradenie pole čísel s časovou zložitosťou O (n ^2). Bude to napríklad selection sort, ktorý v stručnosti nájde vždy minimum v čase O (n) a to vloží na začiatok poľa. Potom nájde ďalšie minimum zo zvyšných prvkov a "vloží" ho za predchádzajúce minimum. Toto urobí tiež n krát, teda výsledná časová zložitosť je O (n * n) = O (n ^2).

Majme potom druhý, úplne hlúpy algoritmus, ktorý bude skúšať všetky permutácie čísel tak dlho, kým pole nebude sežazené. Permutácií bude iste O (n!), Ďalšie operácie pre jednoduchosť zanedbáme, už takto je zložitosť dosť vysoká .

Teraz majme naopak Quicksort, ktorý tu pre jednoduchosť vysvetľovať nebudem, ale dokáže Zotriediť pole s časovou zložitosťou O (n log n).

Pre názornosť si ešte pridáme algoritmus s čas. zložitosťou O (n) a to aj napriek tomu, že sa tak dobre triediace problém zvládnuť nedá.

Predsa len si tentoraz zmerajme čas, ako dlho budú algoritmy triediť pole rôznych veľkostí na jednom, rovnako rýchlom počítači. Budeme predpokladať, že 1 operácia trvá 1ms:

prvkov	O (n)	O (n log n)	O (n 2)	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 rokov
100	0,1 sekundy	0,7 sekundy	10 sekúnd	nevyčíslitené
1000	1 sekundu	10 sekúnd	pol hodiny	nevyčísliteľné

Dajme tomu, že počítač mal frekvenciu procesora 3GHz. Čo keď ho zrýchlime? Tie zlé algoritmy predsa pôjdu potom rýchlejšie, nie? No, nepôjdu. Tu práve vidíme tú kvalitu, hoci algoritmus sa zložitosťou O (n) po 10tich násobnom zrýchlenie počítača zvládne naozaj 10x viac prvkov, ale o tých ďalších to povedať nemôžeme. Tu celkom iste nebude priama úmera, zrýchlenie je len konštanta a keď funkcie rastie moc rýchlo, je konštanta úplne zanedbateľná. Pozrime sa, ako by to vyzeralo, keby sme počítač zrýchlili 10x, 100x a dokonca 1000x:

Dajme tomu, že triedime 15 prvkov (teda podľa predchádzajúcej tabuľky triedime 0,15 sekundy). Pozrime sa, koľko toho za túto dobu stihneme zotrieďiť u ostatných algoritmov a ako si zrýchlením pomôžeme:

frekvencia CPU	O (n)	O (n log n)	O (n 2)	O (n!)
3 GHz (bez zrýchlenia)	15 prvkov	6 prvkov	4 prvky	4 prvky
30 GHz	150 prvkov	30	12 prvkov	5 prvkov
300 GHz	1500 prvkov	200 prvkov	40 prvkov	6 prvkov
3 000 GHz	15000 prvkov	1400 prvkov	120 prvkov	8 prvkov

hodnoty sú zaokrúhlené

Vidíte, že keď zrýchlime počítač 1000krát na takt 3 000 GHz, rovnako si u zložitosti O (n!) Pomôžeme len o obyčajné 4 prvky. Kvalita algoritmu je zlá a zrýchlenie stroja nie je riešenie. Musíme sa poobzerať po inom algoritmu s lepšou časovou zložitosťou.

Čo sme si odniesli? Že časová zložitosť rozdeľuje algoritmy do určitých kvalitatívnych kategórií. A je úplne jedno, či nejaký algoritmus potom miliónkrát zrýchlime, pretože sa aj tak nikdy nedostaneme z onej kategórie a vždy bude existovať taký počet prvkov, od ktorého bude algoritmus z inej kategórie rýchlejší. Inými slovami algoritmus čo triedi čísla v O (n log n) spustený na staručkej 486ce bude treba od poľa veľkosti 1000 a viac vždy rýchlejší, než triediace algoritmus sa zložitosťou O (n ^2), spustený na modernom stojádrovém servera. Zrýchlenie handicap algoritmu na chvíľu skryje, ale s rastúcim vstupom sa vždy stratí, pre dostatočne veľké čísla sa konštanta stane úplne bezvýznamnú. (Zasvätenie teraz spoznali, že som odriekal definíciu limity

Symbol veľké O sa nazýva "veľké O notácie" alebo "Omikron notácie". Znamená, že zložitosť daného algoritmu je asymptoticky menšia alebo rovná výrazu v zátvorke. Udáva teda, akú "triedu časovej zložitosti" algoritmus nikdy neprekročí. Môžete sa tiež stretnúť so symbolmi veľké Omega (väčšie alebo rovné) a tiež s malými ekvivalenty omegy a omikron, ktoré symbolizujú ostrú nerovnosť. Konečne veľké PHI je asymptoticky rovná.

Ďalšie vlastnosti algoritmov

Stabilita

O stabilným algoritmu hovoríme v prípade, keď zachováva doterajšie poradie takých prvkov, ktoré sú si podľa porovnávacieho kritéria rovné. Ak triedime pole čísel, nemá to pre nás žiadny úžitok. Ale vo chvíli, keď triedime napr. Objekty alebo nejaké ďalšie kontajnerové štruktúry, môže sa nám to veľmi hodiť. Dajme tomu, že máme zamestnanca zoradené v poli podľa abecedy. A my ich chceme zoradiť podľa veku. Ak radiacej algoritmus nie je stabilný, môže sa nám stať, že dvaja rovnako starí zamestnanci (Adam a Zdeněk) budú v poradí: Zdeněk, Adam. Stabilné algoritmus naopak v prípade rovnosti zachová pôvodné poradie prvkov, teda Adam, Zdeněk. Zamestnanci s rovnakým vekom teda budú ešte zoradení podľa abecedy.

Na mieste

Hovoríme napr., Že triedime na mieste, ak nepotrebujeme okrem vstupného poľa žiadnu dodatočnú pamäť. Ak áno, vzniká nebezpečenstvo, či budeme mať pamäti vždy dostatok. Za tento pamäťový handicap niekedy môžeme dostať lepšie časovú zložitosť alebo iné výhody. V anglickej literatúre sa stretnete s termínom "In place".

To by bolo asi pre začiatok všetko, teraz si môžete bez problému prechádzať zbierku algoritmov, prítomnú na tomto serveri

U tabuliek som sa inšpiroval materiály Unicorn College od profesora Ondreja Kučeru. V budúcej lekcii, Výpočet časovej zložitosti algoritmu , sa naučíme časovú zložitosť určitého algoritmu spočítať.