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 numbers s 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 i cyklu 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)	4n² + 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ů.

Článek pro vás napsal Ondřej Michálek

Uživatelské hodnocení:

140 hlasů

Autor se věnuje teoretické informatice. Ve svých volných chvílích nepohrdne šálkem dobrého čaje, kaligrafickým brkem a foukací harmonice.

Aktivity

Nejčastěji vyhledáváné

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

Proměnné algoritmu

Použité algoritmy

Prosté prohledání pole

Složitost algoritmu

Nejlepší případ

Nejhorší případ

Naivní prohledávání pole

Složitost algoritmu

Nejlepší případ

Nejhorší případ

Ultrahloupé prohledání pole

Složitost algoritmu

Nejlepší případ

Nejhorší případ

Porovnání algoritmů bez asymptotické notace

Závěr