Lekce 2 - Výpočet časové složitosti algoritmů
V minulé lekci, Úvod do teorie algoritmů, jsme si uvedli teorii algoritmů.
V dnešním tutoriálu o teorii algoritmů si uvedeme a spočítáme časovou složitost pro hledání největšího prvku v poli pomocí různých algoritmů. Budeme se zabývat zejména správným a špatným použitím jednotlivých algoritmů a ukážeme jejich praktické ukázky.
Tento problém je jeden z nejvyskytovanějších problémů ve světě IT (více v lekci Hledání extrému (minima a maxima) v poli).
Proměnné algoritmu
V našem algoritmu použijeme tyto proměnné:
- pole
numberss indexy{0, 1, ..., n-1}, - proměnnou
max_value(maxValue) uchovávající maximální hodnotu v poli, na kterou jsme zatím narazili, - řídící proměnnou
icyklu udržující informaci na jakém indexu v poli se zrovna nacházíme.
Použité algoritmy
Pro hledání největšího prvku v poli si napíšeme algoritmy pro hledání:
- prostým prohledáním pole,
- naivním prohledáním pole,
- ultrahloupým prohledáním pole.
Prosté prohledání pole
Pokud chceme najít největší prvek v poli kladných čísel,
nejjednodušší postup je určit si maximum nejprve na hodnotu 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:
-
max_value = 0 i = 0 while i <= n-1: if numbers[i] > max_value: max_value = numbers[i] i = i + 1 return max_value
-
int maxValue = 0; int i = 0; while (i <= n-1) { if (numbers[i] > maxValue) { maxValue = numbers[i]; } i = i + 1; } return maxValue;
-
$maxValue = 0; $i = 0; while ($i <= $n-1) { if ($numbers[$i] > $maxValue) { $maxValue = $numbers[$i]; } $i = $i + 1; } return $maxValue;
-
int maxValue = 0; int i = 0; while (i <= n-1) { if (numbers[i] > maxValue) { maxValue = numbers[i]; } i = i + 1; } return maxValue;
Nejprve inicializujeme index v poli a maximální nalezenou hodnotu
max_value na 0. Dále definujeme cyklus
while, který kontroluje zda v poli numbers jsou prvky
na kontrolu. Jakmile projdeme celé pole, cyklus skončí.
Na dalším řádku kontrolujeme podmínkou if, zda je
momentální prvek větší, než je dosud známé maximum
max_value. Pokud ano, uložíme současný prvek jako nové
známé maximum. Poté zvýšíme index o hodnotu 1,
abychom se v poli posunuli na další prvek a postupně ho tak celé prošli.
Nakonec vracíme maximum, které je buď 0, nebo maximum z
pole.
Složitost algoritmu
Spočtěme si, jaká bude složitost tohoto algoritmu, tedy kolik uděláme operací.
Inicializaci proměnných provádíme 1-krát protože
inicializujeme pouze na začátku programu. Cyklus while se provede
n-krát jelikož vždy musíme projít celé pole. Prohledáváme
prvek po prvku a nemůžeme si dovolit přeskočit prvek.
Podmínka if se provede n-krát. Prvek se vždy
porovná s proměnnou max_value. Podmínka se provede minimálně
0-krát. Maximálně n-krát se provede, jen pokud je
hodnota v proměnné max_value menší než prvek. Poslední
řádek v cyklu while se provede n-krát, protože
index se zvětší vždy.
Poslední řádek se provede 1-krát, jelikož na konci metody
vrátíme hodnotu max_value jen jednou.
Nyní jednoduše sečteme počet operací. To můžeme udělat, protož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
Nejlepší případ nastane, když by v poli nebylo větší číslo než
0 (tudíž negativní číslo), případně
Integer.MIN. Pak výpočet časové složitosti bude
následující:
1 + n + n + 0 + n + 1 + 1 = 3n + 3 = O(n)
O notaci O() jsme si již říkali v lekci Úvod
do teorie algoritmů. Práce s ní je podobná jako s limity a určuje
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
Nejhorší případě by nastal, když by bylo pole seřazené a my jsme v každém kroku nalezli nové maximum, které bychom museli pokaždé aktualizovat. Složitost pak bude následující:
1 + n + n + n + n + 1 + 1 = 4n + 3 = O(n)
Opravdu si můžeme dovolit všechno sčítat? Podívejme se 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,
- zvýšení indexu.
Tyto operace provedeme nejvýše n-krát. Výsledek
4n tedy opravdu odpovídá skutečnosti.
Naivní prohledávání pole
Kdybychom v poli narazili na větší prvek, než je doposud známé maximum, spustili bychom celý cyklus znovu. Tak bychom procházeli znovu i prvky menší než předchozí maximum. Tyto prvky jsou jistě i menší než nové maximum, a tak se již procházet nemusí.
Kód algoritmu je následující:
-
max_value = 0 i = 0 while i <= n-1: if numbers[i] > max_value: max_value = numbers[i] continue else: i = i + 1 return max_value
-
int maxValue = 0; int i = 0; while (i <= n-1) { if (numbers[i] > maxValue) { maxValue = numbers[i]; continue; } else { i = i + 1; } } return maxValue;
-
$maxValue = 0; $i = 0; while ($i <= $n-1) { if ($numbers[$i] > $maxValue) { $maxValue = $numbers[$i]; continue; } else { $i = $i + 1; } } return $maxValue;
-
int maxValue = 0; int i = 0; while (i <= n-1) { if (numbers[i] > maxValue) { maxValue = numbers[i]; continue; } else { i = i + 1; } } return maxValue;
Nejprve inicializujeme proměnné max_value a i na
hodnotu 0. Poté napíšeme cyklus while, který
končí jakmile projde celé pole. V podmínce if kontrolujeme,
jestli proměnná i v poli numbers je větší než
doposud známé max_value.
Pokud je hodnota proměnné i větší než
max_value, měníme momentální maximum za nový prvek.
Klíčovým slovem continue přeskočíme zbytek cyklu . Pokud
hodnota proměnné i není větší než doposud
známé max_value, tak zvýší index o hodnotu
1.
Nakonec vrátíme maximum, které je buď 0 nebo maximum z
pole.
Složitost algoritmu
Tento algoritmus bude určitě složitější než ten předchozí. Pojďme se o tom přesvědčit a spočítat to 😀
Inicializace se provede jen 1-krát protože inicializujeme
pouze na začátku programu. Podmínka cyklu se provede n-krát,
jelikož vždy musíme projít celé pole numbers a nemůžeme si
dovolit nějaký prvek přeskočit. Podmínka if se provádí
n-krát, protože prvek se vždy porovnává s proměnnou
max_value.
Přiřazení max_value = numbers[i] se provede minimálně
0-krát, maximálně n-krát a provede se jen, pokud
je hodnota proměnné max_value větší než prvek. Příkaz
continue se provede minimálně 1-krát, maximálně
n-krát. Jestliže máme stoupající posloupnost, program pro
každý prvek pojede od začátku.
Řádek s else se provede minimálně 0-krát,
maximálně n-krát. Provede se vždy, pokud se neprovede
max_value = numbers[i]. Tudíž nemůže platit minimum řádku s
kódem max_value = numbers[i]; a zároveň minimum bloku
else. Ve výpočtu proto budeme počítat s minimem pro
max_value = numbers[i]; a maximem pro řádek s blokem
else.
Konec bloku else se provede 1-krát. Vrácení
hodnoty proměnné max_value se provede také
1-krát.
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ě pak bude složitost:
1 + n * ( n + n + n + n + 0 ) + 1 + 1 = 4n^2 + 3 = O(n^2)
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? Protože nejhůře n-krát budeme
dělat to samé, jen s jinými parametry. To je i rada do budoucna. Jakmile
máme více cyklů a v každém cyklu se dělá skoro to samé, zamysleme se,
jak bychom mohli náš program zrychlit.
Ultrahloupé prohledání pole
V posledním příkladu algoritmu si uvedeme opravdu hloupý algoritmus pro
vyhledání maxima v poli. Ten bude dělat to samé, jako algoritmus pomocí
prostého prohledání pole, 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, v které budeme uchovávat hodnotu proměnné
i.
Kód algoritmu je následující:
-
max_value = 0 i = 0 docas = 0 while i <= n-1: if numbers[i] > max_value: max_value = numbers[i] docas = i i = 0 while i < 1000000: i = i + 1 i = docas + 1 return max_value
-
int maxValue = 0; int i = 0; int docas = 0; while (i <= n-1) { if (numbers[i] > maxValue) { maxValue = numbers[i]; } docas = i; i = 0; while (i < 1000000) { i = i + 1; } i = docas + 1; } return maxValue;
-
$maxValue = 0; $i = 0; $docas = 0; while ($i <= $n-1) { if ($numbers[$i] > $maxValue) { $maxValue = $numbers[$i]; } $docas = $i; $i = 0; while ($i < 1000000) { $i = $i + 1; } $i = $docas + 1; } return $maxValue;
-
int maxValue = 0; int i = 0; int docas = 0; while (i <= n-1) { if (numbers[i] > maxValue) { maxValue = numbers[i]; } docas = i; i = 0; while (i < 1000000) { i = i + 1; } i = docas + 1; } return maxValue;
Je to v podstatě algoritmus pomocí prostého prohledání pole. Jediné, co algoritmus dělá navíc, je zbytečné počítání do milionu. Tento cyklus se provede vždy, proto nebudeme rozepisovat řádky a rovnou přejdeme k výpočtu složitosti.
Složitost algoritmu
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
V nejhorším případě je pak složitost:
1 + n + n + n + n + n + 1000000n + 1000000n + n + n + 1 = 2000009n + 3 = O(n)
Asymptoticky jsme na tom tedy stejně jako v algoritmu pomocí prostého prohledání pole. 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
Jestliže porovnáme nejhorší případ bez asymptotické notace s
algoritmem pomocí naivního prohledání pole 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 ale budeme vyhledávat
maximum v poli o velikosti 100, rozhodně vyjde lépe v této
situaci ten asymptoticky horší algoritmus.
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.
V další lekci, Třídy časové složitosti algoritmů a jejich využití, se podíváme na různé třídy časové složitosti algoritmů, jejich využití a určení složitosti jednotlivých algoritmů.
