Big O Notation

V první části tohoto tutoriálu se podíváme, co je to Big O Notation.

Co je to Big O Notation

I když je tento tutoriál o algoritmech a datových strukturách, Big O Notation mezi ně nepatří. Big O Notation představuje jen takový způsob, pomocí kterého můžeme zapsat, jakou má nějaký kód časovou nebo paměťovou náročnost. Slouží tedy jen jako taková informace na kterou se můžeme podívat a zjistit, jak náročný je nějaký kód.

Pomocí Big O Notation zjišťujeme tyto dvě vlastnosti:

• časová náročnost - jak dlouho provedení kódu trvá
• paměťová náročnost - jak velkou část paměti kód zabere

Testování rychlosti kódu

Občas si můžeme chtít zjistit, jakou dobu zhruba trvá provedení nějakého kódu, který jsme napsali. K tomu můžeme použít funkci performance.now, která vrací čas v milisekundách od otevření webové stránky. Nejprve ji zavoláme před provedením nějakého kódu, u kterého chceme změřit jak dlouho bude trvat a podruhé tuto funkci zavoláme po jeho provedení. Čas, který tato funkce vrací si uložíme do proměnných, které od sebe po dokončení kódu odečteme. Tím získáme, jak dlouho provedení nějakého kódu trvá.

// zjištění času před provedením kódu
let cas1 = performance.now();

let pocet = 0;
for (let i = 0; i < 5000000; i++) {
    pocet++;
}

// zjištění času po provedení kódu
let cas2 = performance.now();
console.log(`Provedení kódu trvalo ${cas2 - cas1} milisekund.`);

Čas, který tímto způsobem získáme ale není vůbec přesný. Pokud budeme dobu běhu stejného kódu měřit vícekrát, tak nám vždy vyjde jiný čas. Navíc se doba běhu kódu na různých zařízeních bude lišit. I když ale tento způsob měření není přesný, tak to neznamená že bychom jej nemohli používat. Občas se může hodit si jen tak změřit, jakou dobu zhruba trvá provedení nějakého kódu. Je to ale jen taková informace pro nás. Pokud bychom chtěli časovou náročnost kódu stanovit v nezávislosti na tom, na jakém zařízení a za jakých podmínek se bude kód spouštět, můžeme to stanovit pomocí Big O Notation.

Zápis Big O Notation

Big O Notation píšeme takto: O(nějaký výraz). Uvnitř závorek specifikujeme jakou časovou nebo paměťovou náročnost kód má. Tu nemusíme specifikovat přesně. Pokud má kód časovou náročnost O(10n), tak stačí napsat jen O(n).

Zde jsou popsány tři Big O výrazy, které se často používají:

• O(1) - nezáleží na tom jaký je vstup (např. parametr funkce), kód poběží vždy stejně rychle
• O(n) - čím větší číslo bude na vstupu, tím pomaleji kód poběží
• O(n²) - čím větší číslo bude na vstupu, tím pomaleji kód poběží (velké rozdíly se objeví i při malé změně čísla)

Kromě těchto jednoduchých výrazů se občas také používají nějaké složitější. Používají se například také logaritmy. Pokud jste ale stejně jako já už zapomněli, co to vlastně ty logaritmy jsou, nebo jste se o nich nikdy neučili, vůbec to nevadí. Na následujícím obrázku je graf, který ukazuje různé Big O náročnosti. Pokud v dalších částech tutoriálu narazíte na nějakou Big O Notation, u které nebudete vědět jak náročná je, tak se na tento graf můžete podívat. Nemusíme být na Big O Notation experti, jen potřebujeme vědět co to je a popřípadě si na tomto grafu najít, jak náročný nějaký algoritmus je.

Big O Notation objektů a polí

Jen tak pro zajímavost bychom si zde mohli uvést Big O Notation týkající se operací s objekty a poli.

Objekty

• přidávání hodnot - O(1)
• odstraňování hodnot - O(1)
• hledání hodnoty - O(n) - nehledáme klíč, ale hledáme jestli je hodnota pod nějakým klíčem
• přistupování k hodnotám - O(1)

Pole

• přidávání hodnot - záleží na tom kde (při přidání hodnoty do pole se mění indexy - pokud přidáme hodnotu na konec pole, nemění se žádné indexy, pokud ji přidáme na začátek pole, mění se všechny indexy)
• odstraňování hodnot - záleží na tom kde (při odstraňování hodnoty se mění indexy - pokud odstraňujeme hodnotu ze začátku pole, mění se všechny indexy, pokud ji odstraňujeme z konce pole, nemění se žádné indexy)
• hledání hodnoty - O(n)
• přistupování k hodnotám - O(1)

To by bylo pro tuto část vše. Po přečtení této části byste měli hlavně vědět co to Big O Notation je, že vyjadřuje časovou nebo paměťovou náročnost a jak se píše. Určovat ji umět nemusíte a ani jsme si to zde nezkoušeli. V podstatě si jen občas v dalších částech tutoriálu řekneme, jaké má nějaký algoritmus Big O a to bude vše.