Čo je to Big-O notácia?

Zamysleli ste sa niekedy nad tým, prečo program, ktorý ste napísali, trval tak dlho? Možno by vás zaujímalo, či môžete svoj kód zefektívniť. Pochopenie toho, ako môže kód spustiť, môže váš kód posunúť na vyššiu úroveň. Big-O notácia je užitočný nástroj na výpočet toho, aký efektívny je váš kód.

Čo je to Big-O notácia?

Big-O notácia vám dáva spôsob, ako vypočítať, ako dlho bude trvať spustenie vášho kódu. Môžete fyzicky načasovať, ako dlho trvá spustenie vášho kódu, ale s touto metódou je ťažké zachytiť malé časové rozdiely. Napríklad čas potrebný na spustenie 20 až 50 riadkov kódu je veľmi malý. Vo veľkom programe sa však táto neefektívnosť môže pridať.

Big-O notácia počíta, koľko krokov musí algoritmus vykonať, aby zmeral svoju účinnosť. Prístup k vášmu kódu týmto spôsobom môže byť veľmi efektívny, ak potrebujete vyladiť svoj kód na zvýšenie efektivity. Big-O notácia vám umožní merať rôzne algoritmy podľa počtu krokov, ktoré vyžaduje na spustenie, a objektívne porovnať efektivitu algoritmov.

Ako vypočítate notáciu Big-O

Uvažujme o dvoch funkciách, ktoré počítajú, koľko jednotlivých ponožiek je v zásuvke. Každá funkcia zoberie počet párov ponožiek a vráti počet jednotlivých ponožiek. Kód je napísaný v Pythone, ale to nemá vplyv na to, ako by sme spočítali počet krokov.

Algoritmus 1:

def sockCounter (numberOfPair):
individualSocks = 0
pre x v rozsahu (numberOfPair):
individualSocks = individualSocks + 2
vrátiť jednotlivéPonožky

Algoritmus 2:

def sockCounter (numberOfPair):
spiatočné čísloOfPair * 2

Toto je hlúpy príklad a mali by ste byť schopní ľahko zistiť, ktorý algoritmus je efektívnejší. Ale pre prax si poďme prebehnúť každú.

SÚVISIACE: Aká je funkcia v programovaní?

Aká je funkcia v programovaní?

Ak sa učíte programovať svoj vlastný kód, musíte pochopiť, čo sú to funkcie.

Algoritmus 1 má mnoho krokov:

1. Priradí nulovej hodnote premennej individualSocks.
2. Priradí hodnotu jednej premennej i.
3. Porovnáva hodnotu i s numberOfPair.
4. Pridáva dva do individualSocks.
5. Priradí mu zvýšenú hodnotu individualSocks.
6. Zvyšuje i o jednu.
7. Potom sa opakuje v krokoch 3 až 6 rovnako často ako (indiviualSocks - 1).

Počet krokov, ktoré musíme pre algoritmus jeden dokončiť, možno vyjadriť ako:

4n + 2

Existujú štyri kroky, ktoré musíme n-krát dokončiť. V tomto prípade by sa n rovnalo hodnote numberOfPair. Existujú tiež 2 kroky, ktoré sú dokončené raz.

V porovnaní s tým má algoritmus 2 iba jeden krok. Hodnota numberOfPairs sa vynásobí dvoma. Vyjadrili by sme to ako:

1

Ak to ešte nebolo zrejmé, teraz môžeme ľahko vidieť, že algoritmus 2 je o niečo efektívnejší.

Big-O analýza

Všeobecne platí, že ak sa zaujímate o zápis algoritmu Big-O, zaujíma vás viac celková účinnosť a menej potom jemnozrnná analýza počtu krokov. Pre zjednodušenie zápisu stačí uviesť veľkosť efektívnosti.

Vo vyššie uvedených príkladoch by bol algoritmus 2 vyjadrený ako jeden:

O (1)

Algoritmus 1 by sa ale zjednodušil takto:

O (n)

Táto rýchla snímka nám hovorí, ako je účinnosť algoritmu jeden viazaná na hodnotu n. Čím väčšie číslo, tým viac krokov bude algoritmus musieť dokončiť.

Lineárny kód

Pretože nepoznáme hodnotu n, je vhodnejšie zamyslieť sa nad tým, ako hodnota n ovplyvňuje množstvo kódu, ktorý je potrebné spustiť. V algoritme 1 môžeme povedať, že vzťah je lineárny. Ak zakreslíte počet krokov vs. hodnota n dostanete priamku, ktorá ide hore.

Kvadratický kód

Nie všetky vzťahy sú také jednoduché ako lineárny príklad. Predstavte si, že máte 2D pole a chcete v poli vyhľadať hodnotu. Môžete vytvoriť takýto algoritmus:

def searchForValue (targetValue, arraySearched):
foundTarget = False
pre x v poli
pre y v x:
if (y == targetValue):
foundTarget = True
návrat nájdený cieľ

V tomto príklade počet krokov závisí od počtu polí v arraySearched a počtu hodnôt v každom poli. Zjednodušený počet krokov by teda bol n * n alebo n².

Tento vzťah je kvadratický, čo znamená, že počet krokov v našom algoritme exponenciálne rastie s n. V Big-O notácii by ste to napísali ako:

O (n²)

SÚVISIACE: Užitočné nástroje na kontrolu, čistenie a optimalizáciu súborov CSS

Logaritmický kód

Aj keď existuje veľa ďalších vzťahov, posledný vzťah, na ktorý sa pozrieme, sú logaritmické vzťahy. Na osvieženie pamäte je denníkom číslo exponentová hodnota požadovaná na dosiahnutie čísla, ktoré má základňu. Napríklad:

log 2 (8) = 3

Protokol sa rovná tri, pretože ak by naša základňa bola 2, potrebovali by sme exponentovú hodnotu 3, aby sme sa dostali k číslu 8.

Takže vzťah logaritmickej funkcie je opakom exponenciálneho vzťahu. Keď sa n zvyšuje, na spustenie algoritmu je potrebných menej nových krokov.

Na prvý pohľad sa to zdá byť neintuitívne. Ako môžu kroky algoritmu rásť pomalšie ako n? Dobrým príkladom toho sú binárne vyhľadávania. Uvažujme o algoritme na hľadanie čísla v rade jedinečných hodnôt.

• Začneme hľadaním poľa, ktoré je v poradí od najmenšieho po najväčšie.
• Ďalej skontrolujeme hodnotu v strede poľa.
• Ak je vaše číslo vyššie, vylúčime pri vyhľadávaní nižšie čísla a ak bude číslo nižšie, vylúčime vyššie čísla.
• Teraz sa pozrieme na stredné číslo zostávajúcich čísel.
• Opäť vylúčime polovicu čísel na základe toho, či je naša cieľová hodnota vyššia alebo nižšia ako stredná hodnota.
• V tomto procese budeme pokračovať, kým nenájdeme náš cieľ alebo nezistíme, že sa nenachádza v zozname.

Ako vidíte, keďže binárne vyhľadávania eliminujú pri každom prechode polovicu možných hodnôt, pretože n sa zväčšuje, vplyv na počet koľkokrát skontrolujeme pole je sotva ovplyvnený. Aby sme to vyjadrili zápisom Big-O, napísali by sme:

O (log (n))

Dôležitosť noty Big-O

Big-O nation vám poskytuje rýchly a ľahký spôsob, ako oznámiť, aký efektívny je algoritmus. To uľahčuje rozhodovanie medzi rôznymi algoritmami. To môže byť obzvlášť užitočné, ak používate algoritmus z knižnice a nemusíte nevyhnutne vedieť, ako kód vyzerá.

Keď sa prvýkrát naučíte kódovať, začnete s lineárnymi funkciami. Ako vidíte z grafu vyššie, dostanete sa veľmi ďaleko. Ale keď sa stanete skúsenejšími a začnete vytvárať zložitejší kód, efektívnosť sa začne stávať problémom. Pochopenie toho, ako kvantifikovať efektívnosť vášho kódu, vám poskytne nástroje, ktoré potrebujete, aby ste ho mohli začať vylaďovať na efektívnosť a zvažovať výhody a nevýhody algoritmov.

10 najčastejších chýb pri programovaní a kódovaní

Kódovacie chyby môžu viesť k toľkým problémom. Tieto tipy vám pomôžu vyhnúť sa programovacím chybám a zaistiť zmysluplnosť kódu.

O autorovi