2. diel - Výpočet časovej zložitosti algoritmu

V minulej lekcii, Úvod do teórie algoritmov , sme mali ľahkú ochutnávku toho, prečo by nás mala časová zložitosť nášho kódu zaujímať. Dnes si tento problém rozoberieme podrobnejšie a naučíme sa zistiť akú časovú zložitosť má určitý algoritmus.

Problém hľadanie maxima

Predstavme si napr. Problém hľadania najväčšieho prvku v poli. Koľkokrát musíme prejsť pole, než nájdeme najväčší prvok? Predstavíme si niekoľko algoritmov a spočítame ich časovú zložitosť.

Náš program bude používať nasledujúce premenné:

• pole A s indexmi {0, 1, ..., n-1}
• premenná MAX uchovávajúci maximálnu hodnotu v poli, na ktorú sme zatiaľ narazili. Pre jednoduchosť uvažujme v poli len kladné čísla a teda môžeme na začiatku maximálnu hodnotu vyhlásiť za 0. Ak by sme chceli do poľa uložiť úplne všetky kladné čísla, za MAX by sme zvolili nejakú najmenšiu možnú konštantu, napr. Integer.MIN.
• i ako premenná pre cyklus, udržujúci informáciu na akom indexu v poli sa zrovna nachádzame

A) Prosté prehľadaní poľa

Ak by sme chceli nájsť najväčší prvok v poli kladných čísiel, najjednoduchší postup je určiť si maximum najprv na 0 a potom prejsť pole prvok po prvku. Ak narazíme na väčšie číslo, prehlásime ho za nové maximum. Po prechode tak budeme poznať skutočne najväčšie číslo v poli.

Zodpovedajúci kód tohto algoritmu je nasledujúci:

int MAX = 0, i = 0;
while (i <= n-1) {
    if (A[i] > MAX)
        MAX = A[i];
    i = i + 1;
}
return MAX

Vysvetlenie algoritmu

• Na riadku 1 inicializujeme index v poli a maximálnu nájdenú hodnotu MAX na 0.
• Ďalej definujeme 2 podmienku pre cyklus, ktorý má kontrolovať, že momentálna index v poli nie je väčšia ako najvyšší index. To aby sme nečítali prvky mimo poľa. Ak sa tak stane, cyklus skončí.
• Na riadku 3 kontrolujeme podmienkou, či je momentálna prvok väčší, než je doteraz známe maximum MAX.
• Ak áno, uloží súčasný prvok ako nové známej maximum na riadku 4.
• Riadok 5, ktorý nastane vždy, zvýši index o 1. To aby sme sa v poli posunuli na ďalší prvok a postupne ho tak celé prešli.
• Riadok 6 nám len hovorí, kde cyklus končí.
• Riadok 7 vracia maximum, ktoré je buď 0, alebo maximum z poľa.

Zložitosť

Aká je zložitosť daného algoritmu, teda koľko urobíme operácií?

• Riadok 1 sa vykonáva 1 -krát - inicializujeme iba na začiatku programu
• Riadok 2 sa vykonáva n -krát - vždy musíme prejsť celé pole, prvok po prvku, preto si nemôžeme dovoliť sa na nejaký prvok nepozrieť
• Riadok 3 sa vykonáva n -krát - prvok sa vždy porovnáva s MAX
• Riadok 4 sa vykonáva MINIMÁLNE 0 -krát, MAXIMÁLNE n -krát - vykonáva sa len ak je MAX menšia ako prvok
• Riadok 5 sa vykonáva n -krát - index sa vždy zväčší
• Riadok 6 uskutočňuje 1 -krát - koniec bloku
• Riadok 7 sa vykonáva 1 -krát - na konci funkcie vráti raz hodnotu MAX

Teraz jednoducho sčítame počet operácií, čo môžeme urobiť vďaka tomu, že máme na každom riadku len jednu operáciu. Pre zjednodušenie predpokladajme, že všetky operácie trvajú rovnako dlho.

Najlepší prípad

V najlepšom prípade, keď by v poli nebolo väčšie číslo ako 0, prípadne Integer.MIN, bude časová zložitosť:

1 + n + n + 0 + n + 1 + 1 = 3n + 3 = O(n)

O notáciu O() sme si už hovorili v minulej lekcii, práca s ňou je podobná ako s limitmi a určuje akúsi "kvalitatívne skupinu algoritmu". Zložitosť 3n + 3 krokov môžeme jednoducho vyhlásiť za O(n), čo znamená, že doba behu algoritmu porastie lineárne so zvyšujúcim sa počtom prvkov v poli. Konštanty 3 a 3 nás už toľko netrápi.

Najhorší prípad

V najhoršom prípade, keď by bolo pole zoradené a my sme v každom kroku našli nové maximum, ktoré by sme museli zakaždým aktualizovať, by zložitosť bola:

1 + n + n + n + n + 1 + 1 = 4n + 3 = O(n)

Pozn. naozaj si môžeme dovoliť všetko sčítať? Naposledy sa pozrime na algoritmus a pokúsme sa pozrieť, čo je na čom závislé. Hlavne sa pozrime na náš cyklus. Pri každom priechode cykle môžu nastať najviac 4 operácie: skontrolovanie indexu, porovnanie prvku, priradenie prvku a zvýšenie indexu. Toto urobíme najviac n -krát. Výsledok 4n teda naozaj zodpovedá skutočnosti.

B) Naivný prehľadávanie poľa

Menej skúsených programátorov by mohol napadnúť horší spôsob nájdenie maxima, než aký sme si uviedli vyššie. Keď by v poli narazili na väčší prvok, ako je doteraz známe maximum, spustili by celý cyklus znova. Tak by prechádzali znovu aj prvkami menej ako predchádzajúce maximum, ktoré sú istoiste aj menšie ako nové maximum a tak sa už prechádzať nemusí.

Uveďme si zdrojový kód:

int MAX = 0;
label: int i = 0;
while (i <= n-1) {
    if (A[i] > MAX) {
        MAX  = A[i];
        goto label; }
    else   i = i + 1
}
return MAX;

Vysvetlenie algoritmu

• Na riadkoch 1 a 2 inicializujeme premenné na 0.
• Na začiatku riadku 2 je tzv. Návestí, slúži na to, aby goto vedelo, kam má skočiť.
• Na riadku 3 definujeme podmienku pre cyklus, ktorý má kontrolovať, že momentálna index nie je väčšia ako najvyšší index. Ak áno, tak skončí.
• Na riadku 4 kontrolujeme podmienku toho, či je momentálna prvok väčší, než je doteraz známe maximum.
• Ak áno, vymení momentálnej maximum za nový prvok na riadku 5.
• Na riadku 6 program skočí späť na riadok 2 a začína s novým MAX všetko odznova.
• V riadku 7 zvýšime index i.
• Riadok 8. nám len hovorí, kde cyklus končí.
• Riadok 9 vracia maximum, ktoré je buď 0 alebo maximum z poľa.

Zložitosť

Asi tušíte, že zložitosť sa oproti predchádzajúcemu algoritmu zhorší. Ako zlé to bude? Poďme to spočítať:

• Riadok 1 sa vykonáva 1 -krát - inicializujeme iba na začiatku programu
• Riadok 2 sa vykonáva MINIMÁLNE 1 -krát, MAXIMÁLNE n -krát - ak máme stúpajúca postupnosť, program pre každý prvok pôjde od začiatku
• Riadok 3 sa vykonáva n -krát - vždy musíme prejsť celé pole, preto si nemôžeme dovoliť sa na nejaký prvok nepozrieť
• Riadok 4 sa vykonáva n -krát - prvok sa vždy porovnáva MAX
• Riadok 5 sa vykonáva MINIMÁLNE 0 -krát, MAXIMÁLNE n -krát - vykonáva sa len ak je MAX menšia ako prvok
• Riadok 6 uskutočňuje MINIMÁLNE 0 -krát, MAXIMÁLNE n -krát - vykonáva sa len ak je MAX menšia ako prvok
• Riadok 7 sa vykonáva MINIMÁLNE 0 -krát, MAXIMÁLNE n -krát - tu pozor, vykoná sa vždy, ak sa nevykoná riadok 5, teda nemôže platiť minimum riadku 5 a zároveň minimum riadku 7, vo výpočte preto počítame s minimom riadku 5 a maximom riadku 7.
• Riadok 8 sa vykonáva 1 -krát - koniec bloku
• Riadok 9 sa vykonáva 1 -krát - na konci funkcie vráti raz hodnotu MAX

Najlepší prípad

V najlepšom prípade bude časová zložitosť:

1 + 1 + n + n + 0 + 0 + n + 1 + 1 = 3n + 4 = O(n)

Najhorší prípad

V najhoršom prípade zložitosť bude:

1 + n * ( n + n + n + n + 0 ) + 1 + 1 = 4n^2 + 3 = O(n^2)

Pozn .: Tu vidíme, aký je rozdiel medzi najlepším a najhorším odhadom. A vzhľadom k tomu, že sme pesimisti, tak (takmer) vždy používame najhoršie odhad. O výnimkách sa dozvieme v ďalších lekciách. A prečo násobíme? Keď si uvedomíte, tak najhoršie n -krát budeme robiť to isté, len s inými parametrami. To je aj rada do budúcnosti, akonáhle máte viac cyklov a v každom cykle sa robí skoro to isté, skúste sa zamyslieť, ako by sme mohli náš program zrýchliť.

Malý chaos na záver

V minulej lekcii sme si povedali, že konštanty zanedbávame. V praxi sa ale samozrejme môže stať, že veľmi zle napísaný algoritmus s O(n) bude na danom stroji pomalší, než ten s O(n^2). Notácie O() totiž nezohľadňuje rýchlosť jednotlivých inštrukcií, ale závislosť ich počtu na počte vstupných prvkov.

C) Ultrahloupé prehľadanie poľa

Na záver dnešnej lekcie si vyrobme naozaj hlúpy algoritmus pre vyhľadanie maxima v poli. Ten bude robiť to isté, ako prvý variant, ale v každom kroku navyše napočíta do milióna. Jediný zmysel tohto úkonu je preskúmanie jeho vplyvu na časovú zložitosť. K napočítaných si vyrobíme dočasnú premennú docas, nič dôležité nerobí, len uchováva hodnotu i.

int = 0, i = 0, docas = 0;
while (i <= n-1) {
    if (A[i] > MAX )
        MAX = A[i];
    docas = i;
    i = 0;
    while (i < 1 000 000) {
        i = i +1;
    }
    i = docas + 1;
}
return MAX;

Vysvetlenie algoritmu

Je to v podstate algoritmus a), len sme pridali riadky 5 až 10. Jediné, čo algoritmus robí navyše, je zbytočné počítanie do milióna. Tento cyklus sa vždy vykoná, preto nebudeme rozpisovať riadky a rovno prejdeme k výpočtu zložitosti.

Zložitosť

Každý člen výrazu opäť zodpovedá počtu opakovaní jedného riadku, prvý prvého riadku, druhý druhého atď.

Najlepší prípad

v najlepšom prípade je zložitosť:

1 + n + n + 0 + n + n + 1000000n + 1000000n  + n + n + n + 1 = 2000008n + 3 = O(n)

Najhorší prípad

A čo najhoršieho sa môže stať?

1 + n + n + n + n + n + 1000000n + 1000000n + n + n + 1 = 2000009n + 3 = O(n)

Asymptoticky sme na tom teda rovnako ako v prvom prípade. Aj logicky to dáva zmysel, pretože počítanie do milióna nie je nijako závislé od počtu prvkov poľa a do výslednej zložitosti by sa prejaviť ani nemalo.

Nákupný algoritmov bez asymptotickej notácie

Pokiaľ ale porovnáme najhorší prípad bez asymptotickej notácie s algoritmom b) sa zložitosťou 4n^2 + 3 a tento sa zložitosťou 2000009n + 3, získame nasledujúce počty operácií pre tieto dĺžky poľa:

počet prvkov (n)	4n 2 + 3	2000009n + 3
1	7	2 000 012
10	403	20 000 093
100	40 003	200 000 903
1 000	4 000 003	2 000 009 003
10 000	400 000 003	20 000 090 003
100 000	40 000 000 003	200 000 900 003
1 000 000	4 000 000 000 003	2 000 009 000 003
10 000 000	400 000 000 000 003	20 000 090 000 003

Pre dostatočne veľká n (počet prvkov) vždy vyjde lepšie asymptoticky "lepší" algoritmus, ak si ale budete vyhľadávať maximum v poli o veľkosť 100, rozhodne vyjde lepšie v tejto situácii ten asymptoticky "horšie" algoritmus. Takže všetko s mierou

Poznámka na záver

Náš odhad počtu operácií sme v článku zjednodušili. Porovnávanie dvoch premenných má v procesorových inštrukciách inú zložitosť než cyklus a ten zas inú zložitosť než napr. Súčet. Súčet čísel bude niečo ako add x, podmienečný cyklus ako jmp x. Ale do takých detailov z praktických dôvodov zabehávací. Veď nám stačí iba O(n)