Ce este notația Big-O?

Te-ai întrebat vreodată de ce a durat atât de mult un program pe care l-ai scris? Poate ați dori să știți dacă vă puteți face codul mai eficient. Înțelegerea modului în care rulează codul vă poate aduce codul la nivelul următor. Notarea Big-O este un instrument util pentru a calcula cât de eficient este codul dvs.

Ce este notația Big-O?

Notarea Big-O vă oferă o modalitate de a calcula cât timp va dura pentru a vă rula codul. Puteți calcula fizic cât durează codul dvs. pentru a rula, dar cu această metodă, este greu să prindeți mici diferențe de timp. De exemplu, timpul necesar între 20 și 50 de linii de cod este foarte mic. Cu toate acestea, într-un program mare, aceste ineficiențe se pot adăuga.

Notarea Big-O contează câte pași trebuie să execute un algoritm pentru a evalua eficiența acestuia. Abordarea codului dvs. în acest mod poate fi foarte eficientă dacă trebuie să îl reglați pentru a crește eficiența. Notarea Big-O vă va permite să măsurați diferiți algoritmi în funcție de numărul de pași necesari pentru a rula și să comparați obiectiv eficiența algoritmilor.

Cum calculați notația Big-O

Să luăm în considerare două funcții care contează câte șosete individuale sunt într-un sertar. Fiecare funcție ia numărul de perechi de șosete și returnează numărul de șosete individuale. Codul este scris în Python, dar acest lucru nu afectează modul în care am număra numărul de pași.

Algoritmul 1:

def sockCounter (numberOfPairs):
Sosete individuale = 0
pentru x în intervalul (numberOfPairs):
individualSocks = individualSocks + 2
returnează șosete individuale

Algoritmul 2:

def sockCounter (numberOfPairs):
return numberOfPairs * 2

Acesta este un exemplu prostesc și ar trebui să puteți spune cu ușurință care algoritm este mai eficient. Dar, pentru practică, să trecem prin fiecare.

LEGATE DE: Ce este o funcție în programare?

Ce este o funcție în programare?

Dacă învățați cum să vă programați propriul cod, va trebui să înțelegeți ce funcții sunt.

Algoritmul 1 are mulți pași:

1. Atribuie o valoare zero variabilei individualSocks.
2. Atribuie o valoare de una variabilei i.
3. Compară valoarea lui i cu numberOfPairs.
4. Se adaugă două la individualSocks.
5. Își atribuie valoarea crescută a șosetelor individuale.
6. Crește i cu unul.
7. Apoi trece înapoi prin pașii de la 3 la 6 pentru același număr de ori ca (indiviualSocks - 1).

Numărul de pași pe care trebuie să-i parcurgem pentru algoritmul unu poate fi exprimat ca:

4n + 2

Există patru pași pe care trebuie să-i parcurgem de n ori. În acest caz, n ar fi egală cu valoarea numberOfPairs. Există, de asemenea, 2 pași care se finalizează o dată.

În comparație, algoritmul 2 are doar un pas. Valoarea numberOfPairs este înmulțită cu două. Am exprima asta ca:

1

Dacă nu era deja evident, acum putem vedea cu ușurință că algoritmul 2 este mult mai eficient.

Analiza Big-O

În general, când sunteți interesat de notația Big-O a unui algoritm, sunteți mai interesat de eficiența generală și mai puțin de analiza cu granulație fină a numărului de pași. Pentru a simplifica notația, putem spune doar magnitudinea eficienței.

În exemplele de mai sus, algoritmul 2 ar fi exprimat ca unul:

O (1)

Dar algoritmul 1 ar fi simplificat ca:

Pe)

Acest instantaneu rapid ne spune cum eficiența algoritmului este legată de valoarea lui n. Cu cât numărul este mai mare, cu atât mai mulți pași vor trebui parcurși de algoritm.

Cod liniar

Deoarece nu cunoaștem valoarea lui n, este mai util să ne gândim la modul în care valoarea lui n afectează cantitatea de cod care trebuie să ruleze. În algoritmul 1 putem spune că relația este liniară. Dacă parcelați numărul de pași vs. valoarea lui n obține o linie dreaptă care crește.

Codul Cadratic

Nu toate relațiile sunt la fel de simple ca exemplul liniar. Imaginați-vă că aveți o matrice 2D și doriți să căutați o valoare în matrice. S-ar putea să creați un algoritm ca acesta:

def searchForValue (targetValue, arraySearched):
foundTarget = False
pentru x în tablou Căutat:
pentru y în x:
if (y == targetValue):
foundTarget = Adevărat
return foundTarget

În acest exemplu, numărul de pași depinde de numărul de matrice din arraySearched și de numărul de valori din fiecare matrice. Deci, numărul simplificat de pași ar fi n * n sau n².

Această relație este o relație pătratică, ceea ce înseamnă că numărul de pași din algoritmul nostru crește exponențial cu n. În notația Big-O, ați scrie-o astfel:

O (n²)

LEGATE DE: Instrumente utile pentru verificarea, curățarea și optimizarea fișierelor CSS

Codul logaritmic

Deși există multe alte relații, ultima relație pe care o vom analiza este relațiile logaritmice. Pentru a vă reîmprospăta memoria, jurnalul unui număr este valoarea exponentului necesară pentru a ajunge la un număr dat de o bază. De exemplu:

log 2 (8) = 3

Jurnalul este egal cu trei, deoarece dacă baza noastră ar fi 2, am avea nevoie de o valoare a exponentului 3 pentru a ajunge la numărul 8.

Deci, relația unei funcții logaritmice este opusul unei relații exponențiale. Cu cât n crește, sunt necesari mai puțini pași noi pentru a rula algoritmul.

La o primă vedere, acest lucru pare contra-intuitiv. Cum pot pașii unui algoritm să crească mai lent decât n? Un bun exemplu în acest sens sunt căutările binare. Să luăm în considerare un algoritm pentru a căuta un număr într-o serie de valori unice.

• Vom începe cu o matrice de căutare care este în ordine de la cel mai mic la cel mai mare.
• Apoi, vom verifica valoarea din mijlocul matricei.
• Dacă numărul dvs. este mai mare, vom exclude numerele mai mici din căutarea noastră și dacă numărul a fost mai mic, vom exclude numerele mai mari.
• Acum, vom analiza numărul de mijloc al numerelor rămase.
• Din nou, vom exclude jumătate din numere în funcție de faptul dacă valoarea țintă este mai mare sau mai mică decât valoarea medie.
• Vom continua acest proces până când ne vom găsi ținta sau vom stabili că nu se află în listă.

După cum puteți vedea, deoarece căutările binare elimină jumătate din valorile posibile la fiecare trecere, pe măsură ce n devine mai mare, efectul asupra numărului de ori în care verificăm matricea este abia afectat. Pentru a exprima acest lucru în notația Big-O, am scrie:

O (jurnal (n))

Importanța notării Big-O

Națiunea Big-O vă oferă o modalitate rapidă și ușoară de a comunica cât de eficient este un algoritm. Acest lucru face mai ușor să decideți între diferiți algoritmi. Acest lucru poate fi deosebit de util dacă utilizați un algoritm dintr-o bibliotecă și nu știți neapărat cum arată codul.

Când înveți prima dată să codezi, începi cu funcții liniare. După cum puteți vedea din graficul de mai sus, acest lucru vă va duce foarte departe. Dar pe măsură ce devii mai experimentat și începi să construiești un cod mai complex, eficiența începe să devină o problemă. O înțelegere a modului de cuantificare a eficienței codului dvs. vă va oferi instrumentele de care aveți nevoie pentru a începe să-l reglați pentru eficiență și să cântăriți argumentele pro și contra algoritmilor.

10 Cele mai frecvente greșeli de programare și codificare

Greșelile de codare pot duce la atâtea probleme. Aceste sfaturi vă vor ajuta să evitați greșelile de programare și să vă mențineți codul semnificativ.

Despre autor