Čo je to Big-O notácia?

Čo je to Big-O notácia?

Zamysleli ste sa niekedy nad tým, prečo spustenie programu, ktorý ste napísali, trvalo tak dlho? Možno by vás zaujímalo, či môžete váš kód zefektívniť. Pochopenie toho, ako spustenie kódu môže váš kód posunúť na ďalšiu úroveň. Big-O notation je užitočný nástroj na výpočet účinnosti kódu v skutočnosti.





Čo je to Big-O notácia?

Big-O notation vám dáva spôsob, ako vypočítať, ako dlho bude trvať spustenie kódu. Fyzicky môžete načasovať, ako dlho trvá spustenie kódu, ale pri tejto metóde je ťažké zachytiť malé časové rozdiely. Napríklad čas, ktorý trvá 20 až 50 riadkov kódu, je veľmi malý. Vo veľkom programe sa však tieto neefektívnosti môžu sčítať.



tmavý režim prieskumníka súborov systému Windows 10

Big-O notácia počíta, koľko krokov musí algoritmus vykonať, aby zistil svoju účinnosť. Pristupovanie k tomuto kódu týmto spôsobom môže byť veľmi účinné, ak potrebujete svoj kód vyladiť tak, aby zvýšil efektivitu. Big-O notation vám umožní merať rôzne algoritmy podľa počtu krokov, ktoré je potrebné na spustenie, a objektívne porovnať účinnosť 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 vezme 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 počítali počet krokov.

Algoritmus 1:



def sockCounter(numberOfPairs):
individualSocks = 0
for x in range(numberOfPairs):
individualSocks = individualSocks + 2
return individualSocks

Algoritmus 2:

def sockCounter(numberOfPairs):
return numberOfPairs * 2

Toto je hlúpy príklad a mali by ste byť schopní ľahko zistiť, ktorý algoritmus je efektívnejší. Ale precvičme si každú z nich.



SÚVISIACE: Čo je funkcia v programovaní?

Algoritmus 1 má mnoho krokov:



  1. Premennej individualSocks priradí hodnotu nula.
  2. Premennej i priradí hodnotu jedna.
  3. Porovnáva hodnotu i s numberOfPairs.
  4. K jednotlivým ponožkám pridá dve.
  5. Priradí k sebe zvýšenú hodnotu individualSocks.
  6. Zvyšuje sa to po jednom.
  7. Potom sa opakuje v krokoch 3 až 6 rovnako často ako (indiviualSocks - 1).

Počet krokov, ktoré musíme vykonať pre jeden algoritmus, môžeme vyjadriť ako:

4n + 2

Existujú štyri kroky, ktoré musíme vykonať n krát. V tomto prípade by sa n rovná hodnote numberOfPairs. K dispozícii sú tiež 2 kroky, ktoré sú dokončené raz.

Na porovnanie, algoritmus 2 má iba jeden krok. Hodnota numberOfPairs sa vynásobí dvoma. Vyjadríme to takto:

1

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

Big-O analýza

Všeobecne platí, že keď vás zaujíma Big-O zápis algoritmu, zaujíma vás viac celková efektivita, a už vôbec nie jemnozrnná analýza počtu krokov. Na zjednodušenie zápisu môžeme uviesť iba veľkosť účinnosti.

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

O(1)

Algoritmus 1 by však bol zjednodušený ako:

O(n)

Tento rýchly prehľad nám hovorí, ako je účinnosť algoritmu jeden viazaná na hodnotu n. Čím vyššie číslo, tým viac krokov bude musieť algoritmus dokončiť.

Lineárny kód

Obrazový kredit: Nick Fledderus/ Podstatné meno Projekt

Pretože nepoznáme hodnotu n, je užitočnejš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 vykreslíte počet krokov vs. hodnotu n, dostanete priamku, ktorá stúpa.

Kvadratický kódex

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

def searchForValue(targetValue, arraySearched):
foundTarget = False
for x in arraySearched:
for y in x:
if(y == targetValue):
foundTarget = True
return foundTarget

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

koľko stojí netflix mesačne

Obrazový kredit: Nick Fledderus/ Podstatné meno Projekt

Tento vzťah je kvadratický vzťah, čo znamená, že počet krokov v našom algoritme exponenciálne rastie s n. V notácii Big-O by ste to zapí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 mnoho ďalších vzťahov, posledný vzťah, na ktorý sa pozrieme, je logaritmický vzťah. Na obnovenie pamäte je denník čísla hodnotou exponentu potrebného na dosiahnutie čísla na základe základu. Napríklad:

log 2 (8) = 3

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

Obrazový kredit: Nick Fledderus/ Podstatné meno Projekt

Vzťah logaritmickej funkcie je opakom exponenciálneho vzťahu. Ako sa zvyšuje n, na spustenie algoritmu je potrebných menej nových krokov.

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

  • Začneme poľom na vyhľadávanie, 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 nižšie čísla z nášho vyhľadávania a ak bolo číslo nižšie, vylúčime vyššie čísla.
  • Teraz sa pozrieme na stredné číslo zostávajúcich čísel.
  • Opäť vylúčime polovicu čísel podľa 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 svoj cieľ alebo nezistíme, že nie je v zozname.

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

O(log(n))

Dôležitosť notácie Big-O

Big-O nation vám ponúka rýchly a ľahký spôsob komunikácie, ako účinný 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 nevyhnutne neviete, ako kód vyzerá.

ako hrať hru playstation na počítači

Keď sa prvýkrát naučíte kódovať, začnete s lineárnymi funkciami. Ako vidíte z vyššie uvedeného grafu, dostanete sa veľmi ďaleko. Ale ako sa stanete skúsenejšími a začnete vytvárať komplexnejší kód, z efektívnosti začína byť problém. Pochopenie toho, ako kvantifikovať účinnosť kódu, vám poskytne nástroje, ktoré potrebujete na to, aby ste ho začali ladiť na efektívnosť a zvážili výhody a nevýhody algoritmov.

zdieľam zdieľam Tweet E -mail 10 najčastejších chýb pri programovaní a kódovaní

Kódovanie chýb môže viesť k mnohým problémom. Tieto tipy vám pomôžu vyhnúť sa chybám pri programovaní a zachovať zmysel kódu.

Čítajte ďalej Súvisiace témy
  • Programovanie
  • Programovanie
O autorovi Jennifer Seaton(21 publikovaných článkov)

J. Seaton je vedecký spisovateľ, ktorý sa špecializuje na delenie zložitých tém. Má doktorát z University of Saskatchewan; jej výskum sa zameral na využitie učenia sa na základe hier na zvýšenie zapojenia študentov online. Keď nepracuje, nájdete ju pri jej čítaní, hraní videohier alebo záhradníctve.

Viac od Jennifer Seaton

prihlásiť sa ku odberu noviniek

Pripojte sa k nášmu bulletinu a získajte technické tipy, recenzie, bezplatné elektronické knihy a exkluzívne ponuky!

Kliknutím sem sa prihlásite na odber