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 za0
. Pokud bychom chtěli do pole uložit úplně všechna kladná čísla, zaMAX
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
na0
. - 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á sMAX
- Řádek 4 se provádí MINIMÁLNĚ
0
-krát, MAXIMÁLNĚn
-krát - provádí se jen pokud jeMAX
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 hodnotuMAX
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 jeMAX
menší než prvek - Řádek 6 se provádí MINIMÁLNĚ
0
-krát, MAXIMÁLNĚn
-krát - provádí se jen pokud jeMAX
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 hodnotuMAX
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.