Lekce 2 - Výpočet časové složitosti algoritmu

V minulé lekci, Úvod do teorie algoritmů, jsme měli lehkou ochutnávku toho, proč by nás měla časová složitost našeho kódu zajímat.

Dnes si tento problém rozebereme podrobněji a naučíme se zjistit jakou časovou složitost má určitý algoritmus.

Problém hledání maxima

Představme si např. problém hledání největšího prvku v poli. Kolikrát musíme projít pole, než najdeme největší prvek? Představíme si několik algoritmů a spočítáme jejich časovou složitost.

Náš program bude používat následující proměnné:

• pole A s indexy {0, 1, ..., n-1}
• proměnná MAX uchovávající maximální hodnotu v poli, na kterou jsme zatím narazili. Pro jednoduchost uvažujme v poli jen kladná čísla a tudíž můžeme na začátku maximální hodnotu prohlásit za 0. Pokud bychom chtěli do pole uložit úplně všechna kladná čísla, za MAX bychom zvolili nějakou nejmenší možnou konstantu, např. Integer.MIN.
• i jako proměnná pro cyklus, udržující informaci na jakém indexu v poli se zrovna nacházíme

a) Prosté prohledání pole

Pokud bychom chtěli najít největší prvek v poli kladných čísel, nejjednodušší postup je určit si maximum nejprve na 0 a poté projít pole prvek po prvku. Pokud narazíme na větší číslo, prohlásíme jej za nové maximum. Po průchodu tak budeme znát skutečně největší číslo v poli.

Odpovídající kód tohoto algoritmu je následující:

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

Vysvětlení algoritmu

• Na řádku 1 inicializujeme index v poli a maximální nalezenou hodnotu MAX na 0.
• Dále definujeme 2 podmínku pro cyklus, který má kontrolovat, že momentální index v poli není větší než nejvyšší index. To abychom nečetli prvky mimo pole. Pokud se tak stane, cyklus skončí.
• Na řádku 3 kontrolujeme podmínkou, zda je momentální prvek větší, než je dosud známé maximum MAX.
• Pokud ano, uloží současný prvek jako nové známé maximum na řádku 4.
• Řádek 5, který nastane vždy, zvýší index o 1. To abychom se v poli posunuli na další prvek a postupně ho tak celé prošli.
• Řádek 6 nám jen říká, kde cyklus končí.
• Řádek 7 vrací maximum, které je buď 0, nebo maximum z pole.

Složitost

Jaká je složitost daného algoritmu, tedy kolik uděláme operací?

• Řádek 1 se provádí 1-krát - inicializujeme pouze na začátku programu
• Řádek 2 se provádí n-krát - vždy musíme projít celé pole, prvek po prvku, proto si nemůžeme dovolit se na nějaký prvek nepodívat
• Řádek 3 se provádí n-krát - prvek se vždy porovnává s MAX
• Řádek 4 se provádí MINIMÁLNĚ 0-krát, MAXIMÁLNĚ n-krát - provádí se jen pokud je MAX menší než prvek
• Řádek 5 se provádí n-krát - index se vždy zvětší
• Řádek 6 se provádí 1-krát - konec bloku
• Řádek 7 se provádí 1-krát - na konci funkce vrátí jednou hodnotu MAX

Nyní jednoduše sečteme počet operací, což můžeme udělat díky tomu, že máme na každém řádku jen jednu operaci. Pro zjednodušení předpokládejme, že všechny operace trvají stejně dlouho.

Nejlepší případ

V nejlepším případě, když by v poli nebylo větší číslo než 0, případně Integer.MIN, bude časová složitost:

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

O notaci O() jsme si již říkali v minulé lekci, práce s ní je podobná jako s limitami a určuje jakousi "kvalitativní skupinu algoritmu". Složitost 3n + 3 kroků můžeme jednoduše prohlásit za O(n), což znamená, že doba běhu algoritmu poroste lineárně se zvyšujícím se počtem prvků v poli. Konstanty 3 a 3 nás již tolik netrápí.

Nejhorší případ

V nejhorším případě, když by bylo pole seřazené a my jsme v každém kroku nalezli nové maximum, které bychom museli pokaždé aktualizovat, by složitost byla:

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

Pozn. opravdu si můžeme dovolit všechno sčítat? Naposledy se podívejme na algoritmus a pokusme se podívat, co je na čem závislé. Hlavně se podívejme na náš cyklus. Při každém průchodu cyklu mohou nastat nejvýše 4 operace: zkontrolování indexu, porovnání prvku, přiřazení prvku a zvýšení indexu. Toto uděláme nejvýše n-krát. Výsledek 4n tedy opravdu odpovídá skutečnosti.

b) Naivní prohledávání pole

Méně zkušené programátory by mohl napadnout horší způsob nalezení maxima, než jaký jsme si uvedli výše. Když by v poli narazili na větší prvek, než je doposud známé maximum, spustili by celý cyklus znovu. Tak by procházeli znovu i prvky menší než předchozí maximum, které jsou jistojistě i menší než nové maximum a tak se již procházet 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;

Vysvětlení algoritmu

• Na řádcích 1 a 2 inicializujeme proměnné na 0.
• Na začátku řádku 2 je tzv. návěstí, slouží k tomu, aby goto vědělo, kam má skočit.
• Na řádku 3 definujeme podmínku pro cyklus, který má kontrolovat, že momentální index není větší než nejvyšší index. Pokud ano, tak skončí.
• Na řádku 4 kontrolujeme podmínku toho, zda je momentální prvek větší, než je dosud známé maximum.
• Pokud ano, vymění momentální maximum za nový prvek na řádku 5.
• Na řádku 6 program skočí zpátky na řádek 2 a začíná s novým MAX vše od znova.
• V řádku 7 zvýšíme index i.
• Řádek 8. nám jen říká, kde cyklus končí.
• Řádek 9 vrací maximum, které je buď 0 nebo maximum z pole.

Složitost

Asi tušíte, že složitost se oproti předchozímu algoritmu zhorší. Jak špatné to bude? Pojďme to spočítat:

• Řádek 1 se provádí 1-krát - inicializujeme pouze na začátku programu
• Řádek 2 se provádí MINIMÁLNĚ 1-krát, MAXIMÁLNĚ n-krát - pokud máme stoupající posloupnost, program pro každý prvek pojede od začátku
• Řádek 3 se provádí n-krát - vždy musíme projít celé pole, proto si nemůžeme dovolit se na nějaký prvek nepodívat
• Řádek 4 se provádí n-krát - prvek se vždy porovnává MAX
• Řádek 5 se provádí MINIMÁLNĚ 0-krát, MAXIMÁLNĚ n-krát - provádí se jen pokud je MAX menší než prvek
• Řádek 6 se provádí MINIMÁLNĚ 0-krát, MAXIMÁLNĚ n-krát - provádí se jen pokud je MAX menší než prvek
• Řádek 7 se provádí MINIMÁLNĚ 0-krát, MAXIMÁLNĚ n-krát - tady pozor, provede se vždy, pokud se neprovede řádek 5, tudíž nemůže platit minimum řádku 5 a zároveň minimum řádku 7, ve výpočtu proto počítáme s minimem řádku 5 a maximem řádku 7.
• Řádek 8 se provádí 1-krát - konec bloku
• Řádek 9 se provádí 1-krát - na konci funkce vrátí jednou hodnotu MAX

Nejlepší případ

V nejlepším případě bude časová složitost:

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

Nejhorší případ

V nejhorším případě složitost bude:

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

Pozn.: Zde vidíme, jaký je rozdíl mezi nejlepším a nejhorším odhadem. A vzhledem k tomu, že jsme pesimisté, tak (téměř) vždy používáme nejhorší odhad. O výjimkách se dozvíme v dalších lekcích. A proč násobíme? Když si uvědomíte, tak nejhůře n-krát budeme dělat to samé, jen s jinými parametry. To je i rada do budoucna, jakmile máte více cyklů a v každém cyklu se dělá skoro to samé, zkuste se zamyslet, jak bychom mohli náš program zrychlit.

Malý chaos na závěr

V minulé lekci jsme si řekli, že konstanty zanedbáváme. V praxi se ale samozřejmě může stát, že velmi špatně napsaný algoritmus s O(n) bude na daném stroji pomalejší, než ten s O(n^2). Notace O() totiž nezohledňuje rychlost jednotlivých instrukcí, ale závislost jejich počtu na počtu vstupních prvků.

c) Ultrahloupé prohledání pole

Na závěr dnešní lekce si vyrobme opravdu hloupý algoritmus pro vyhledání maxima v poli. Ten bude dělat to samé, jako první varianta, ale v každém kroku navíc napočítá do milionu. Jediný smysl tohoto úkonu je prozkoumání jeho vlivu na časovou složitost. K napočítání si vyrobíme dočasnou proměnnou docas, nic důležitého nedělá, jen uchovává 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;

Vysvětlení algoritmu

Je to v podstatě algoritmus a), jen jsme přidali řádky 5 až 10. Jediné, co algoritmus dělá navíc, je zbytečné počítání do milionu. Tento cyklus se vždy provede, proto nebudeme rozepisovat řádky a rovnou přejdeme k výpočtu složitosti.

Složitost

Každý člen výrazu opět odpovídá počtu opakování jednoho řádku, první prvního řádku, druhý druhého atd.

Nejlepší případ

v nejlepším případě je složitost:

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

Nejhorší případ

A co nejhoršího se může stát?

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

Asymptoticky jsme na tom tedy stejně jako v prvním případě. I logicky to dává smysl, protože počítání do milionu není nijak závislé na počtu prvků pole a do výsledné složitosti by se projevit ani nemělo.

Porovnání algoritmů bez asymptotické notace

Pokud ale porovnáme nejhorší případ bez asymptotické notace s algoritmem b) se složitostí 4n^2 + 3 a tento se složitostí 2000009n + 3, získáme následující počty operací pro tyto délky pole:

počet prvků (n)	4n2 + 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

Pro dostatečně velká n (počet prvků) vždy vyjde lépe asymptoticky "lepší" algoritmus, pokud si ale budete vyhledávat maximum v poli o velikost 100, rozhodně vyjde lépe v této situaci ten asymptoticky "horší" algoritmus. Takže všeho s mírou

Poznámka na závěr

Náš odhad počtu operací jsme v článku zjednodušili. Porovnávání dvou proměnných má v procesorových instrukcích jinou složitost než cyklus a ten zas jinou složitost než např. součet. Součet čísel bude něco jako add x, podmíněný cyklus jako jmp x. Ale do takových detailů z praktických důvodů nezabíháme. Vždyť nám stačí pouhé O(n)

V další lekci, Časové složitosti algoritmů a triky pro její odhad, se podíváme na časové složitosti algoritmů a triky pro její odhad.