Co je Big-O notace?

Přemýšleli jste někdy, proč program, který jste napsali, trval tak dlouho? Možná byste chtěli vědět, jestli můžete svůj kód zefektivnit. Pochopení, jak běží kód, může přinést váš kód na další úroveň. Big-O notace je užitečný nástroj pro výpočet efektivity vašeho kódu.

Co je Big-O notace?

Big-O notace vám dává způsob, jak vypočítat, jak dlouho bude trvat spuštění vašeho kódu. Můžete fyzicky měřit, jak dlouho trvá spuštění kódu, ale s touto metodou je těžké zachytit malé časové rozdíly. Například čas mezi 20 a 50 řádky kódu je velmi malý. Ve velkém programu se však tyto neefektivity mohou přidat.

Big-O notace počítá, kolik kroků musí algoritmus provést, aby změřil svou účinnost. Přístup k vašemu kódu tímto způsobem může být velmi efektivní, pokud potřebujete vyladit svůj kód pro zvýšení efektivity. Big-O notace vám umožní měřit různé algoritmy podle počtu kroků, které vyžaduje ke spuštění, a objektivně porovnat účinnost algoritmů.

Jak vypočítáte notaci Big-O

Zvažme dvě funkce, které počítají, kolik jednotlivých ponožek je v zásuvce. Každá funkce zjišťuje počet párů ponožek a vrací počet jednotlivých ponožek. Kód je napsán v Pythonu, ale to nemá vliv na to, jak bychom spočítali počet kroků.

Algoritmus 1:

def sockCounter (numberOfPairs):
individualSocks = 0
pro x v rozsahu (numberOfPair):
individualSocks = individualSocks + 2
vrátit individuální ponožky

Algoritmus 2:

def sockCounter (numberOfPairs):
návratové čísloOfPair * 2

Toto je hloupý příklad a měli byste být schopni snadno zjistit, který algoritmus je účinnější. Ale pro praxi si projdeme každý.

PŘÍBUZNÝ: Co je funkce v programování?

Co je funkce v programování?

Pokud se učíte programovat svůj vlastní kód, musíte pochopit, jaké funkce jsou.

Algoritmus 1 má mnoho kroků:

1. Přiřadí hodnotu nula proměnné individualSocks.
2. Přiřadí hodnotu jedné proměnné i.
3. Porovnává hodnotu i s numberOfPairs.
4. Přidává dva do individualSocks.
5. Přiřazuje zvýšenou hodnotu individualSocks sám sobě.
6. Zvyšuje se o jednu.
7. Poté provede smyčky kroky 3 až 6 stejným počtem opakování jako (indiviualSocks - 1).

Počet kroků, které musíme u algoritmu jeden provést, lze vyjádřit jako:

4n + 2

Existují čtyři kroky, které musíme nkrát dokončit. V tomto případě by se n rovnalo hodnotě numberOfPairů. Existují také 2 kroky, které jsou dokončeny jednou.

Ve srovnání má algoritmus 2 jen jeden krok. Hodnota numberOfPairs se vynásobí dvěma. Vyjádřili bychom to jako:

1

Pokud to ještě nebylo zřejmé, můžeme nyní snadno vidět, že algoritmus 2 je o něco efektivnější.

Big-O analýza

Obecně platí, že pokud vás zajímá Big-O notace algoritmu, zajímá vás více celková účinnost a méně pak jemnozrnná analýza počtu kroků. Pro zjednodušení zápisu můžeme pouze uvést velikost účinnosti.

Ve výše uvedených příkladech by byl algoritmus 2 vyjádřen jako jeden:

O (1)

Algoritmus 1 by se ale zjednodušil jako:

Na)

Tento rychlý snímek nám říká, jak je účinnost algoritmu jeden vázána na hodnotu n. Čím větší je počet, tím více kroků bude algoritmus potřebovat k dokončení.

Lineární kód

Protože neznáme hodnotu n, je užitečnější přemýšlet o tom, jak hodnota n ovlivňuje množství kódu, který je třeba spustit. V algoritmu 1 můžeme říci, že vztah je lineární. Pokud vykreslíte počet kroků vs. hodnota n dostanete přímku, která jde nahoru.

Kvadratický kód

Ne všechny vztahy jsou tak jednoduché jako lineární příklad. Představte si, že máte 2D pole a chcete vyhledat hodnotu v poli. Můžete vytvořit takový algoritmus:

def searchForValue (targetValue, arraySearched):
foundTarget = False
pro x v poli
pro y v x:
if (y == targetValue):
foundTarget = True
return foundTarget

V tomto příkladu počet kroků závisí na počtu polí v arraySearched a počtu hodnot v každém poli. Zjednodušený počet kroků by tedy byl n * n nebo n².

Tento vztah je kvadratický, což znamená, že počet kroků v našem algoritmu exponenciálně roste s n. V zápisu Big-O byste jej napsali jako:

O (n²)

PŘÍBUZNÝ: Užitečné nástroje pro kontrolu, čištění a optimalizaci souborů CSS

Logaritmický kód

I když existuje mnoho dalších vztahů, poslední vztah, na který se podíváme, je logaritmický vztah. Chcete-li obnovit paměť, protokol čísla je exponentová hodnota potřebná k dosažení čísla daného základu. Například:

log 2 (8) = 3

Protokol se rovná tři, protože pokud by naše základna byla 2, potřebovali bychom exponentovou hodnotu 3, abychom se dostali k číslu 8.

Vztah logaritmické funkce je tedy opakem exponenciálního vztahu. Jak se n zvyšuje, ke spuštění algoritmu je zapotřebí méně nových kroků.

Na první pohled to vypadá protiintuitivně. Jak mohou kroky algoritmu růst pomaleji než n? Dobrým příkladem toho jsou binární vyhledávání. Zvažme algoritmus pro hledání čísla v poli jedinečných hodnot.

• Začneme vyhledávacím polem v pořadí od nejmenšího k největšímu.
• Dále zkontrolujeme hodnotu uprostřed pole.
• Pokud je vaše číslo vyšší, vyloučíme nižší čísla z našeho vyhledávání a pokud bylo číslo nižší, vyloučíme vyšší čísla.
• Nyní se podíváme na střední číslo zbývajících čísel.
• Opět vyloučíme polovinu čísel na základě toho, zda je naše cílová hodnota vyšší nebo nižší než střední hodnota.
• V tomto procesu budeme pokračovat, dokud nenajdeme náš cíl nebo neurčíme, že není v seznamu.

Jak vidíte, protože binární vyhledávání eliminuje při každém průchodu polovinu možných hodnot, protože n se zvětšuje, vliv na počet, kolikrát pole zkontrolujeme, je sotva ovlivněn. Abychom to vyjádřili v zápisu Big-O, napsali bychom:

O (log (n))

Důležitost notace Big-O

Big-O nation vám poskytuje rychlý a snadný způsob, jak sdělit, jak efektivní je algoritmus. To usnadňuje rozhodování mezi různými algoritmy. To může být obzvláště užitečné, pokud používáte algoritmus z knihovny a nemusíte nutně vědět, jak vypadá kód.

Když se poprvé naučíte kódovat, začnete s lineárními funkcemi. Jak vidíte z výše uvedeného grafu, dostanete se velmi daleko. Ale jak se stanete zkušenějšími a začnete vytvářet složitější kód, efektivita se začne stávat problémem. Pochopení toho, jak kvantifikovat účinnost vašeho kódu, vám poskytne nástroje, které potřebujete k jeho vyladění pro efektivitu a zvážení výhod a nevýhod algoritmů.

10 Nejčastější chyby v programování a kódování

Kódovací chyby mohou vést k mnoha problémům. Tyto tipy vám pomohou vyhnout se chybám v programování a udržet váš kód smysluplný.

O autorovi