Notarea mare o în structura datelor: Tot ce trebuie știut

Notația Big O într-o structură de date este utilizată pentru a determina eficiența unui algoritm, timpul necesar pentru a rula funcția odată cu creșterea intrării și cât de bine se scalează funcția. Măsurarea acestei eficiențe poate fi împărțită în două părți, și anume, complexitatea spațiului și complexitatea timpului.

Notația Big O se referă la notația matematică care acționează ca un factor limitator al oricărei funcții atunci când un argument este mai predispus să se încline spre o anumită valoare sau infinit. Aparține categoriei de notații matematice inventate de Edmund Landau, Paul Bachmann și alții. Prin urmare, este denumită în mod colectiv notația Bachmann-Landau sau notația asimptotică.

Conform deducției matematice, două funcții, f(n) și g(n) sunt definite pe o mulțime de numere pozitive sau reale care nu sunt legate. Aici, g(n) este strict pozitiv pentru fiecare valoare mare a lui n. Poate fi scris în felul următor:

f(n) = O(g(n)) în care n tinde spre infinit (n → ∞)

Totuși, aici, ipoteza lui n la infinit nu este definită exclusiv și expresia de mai sus poate fi, prin urmare, scrisă ca:

f(n) = O(g(n))

Aici, f și g sunt funcțiile necesare care încep de la numere întregi pozitive la numere reale care nu sunt negative.

Prin urmare, valorile n mari sunt notate cu Big O asimptotic.

Proprietăți ale notării Big O în structura datelor

Algoritmul Big O în structura datelor are destul de multe proprietăți obligatorii. Proprietățile esențiale menționate ale notării Big O sunt următoarele:

• Funcția de însumare:
  Dacă f(n) = f 1 (n) + f 2 (n) + — + f m (n) și f i (n)≤ f i +1(n) ∀ i=1, 2,–, m,
  atunci O(f(n)) = O(max(f1(n), f2(n), –, fm(n))).
• Funcția logaritmică:
  Dacă f(n) = logan și g(n)=logbn,
  atunci O(f(n))=O(g(n))
• Înmulțire constantă:
  Dacă f(n) = cg(n), atunci O(f(n)) = O(g(n)) în care c este o constantă diferită de zero.
• Funcția polinomială:
  Dacă f(n) = a0 + a1.n + a2.n2 + — + am.nm,
  atunci O(f(n)) = O(nm).

Învață cursuri de dezvoltare software online de la cele mai bune universități din lume. Câștigați programe Executive PG, programe avansate de certificat sau programe de master pentru a vă accelera cariera.

Explorați cursurile noastre populare de inginerie software

Aici, în timp ce se adresează Big O, fiecare funcție de jurnal crește în mod similar.

Importanța notării Big O în analiza timpului de rulare a algoritmilor

Complexitățile timpului de rulare în cel mai rău caz al algoritmului sunt folosite pentru a face comparații și a calcula, mai ales în cazul analizării performanței unui algoritm. Ordinea lui O(1), descrisă ca timp de rulare constant, este cel mai rapid timp de rulare al algoritmului – timpul pe care îl ia algoritmul este același pentru diferite dimensiuni de intrare. Este important de remarcat că timpul de rulare ideal al unui algoritm este timpul de rulare constant, care este foarte rar atins deoarece timpul de rulare al algoritmului depinde de dimensiunea de intrare a lui n.

De exemplu:

După cum sa menționat mai sus, performanța de rulare a unui algoritm depinde în mare măsură de mărimea intrării lui n. Să elucidăm acest fapt cu câteva exemple matematice pentru a face analiza timpului de rulare a unui algoritm pentru diferite dimensiuni ale lui n:

• n = 20
  log (20) = 2,996;
  20 = 20;
  20 log (20) = 59,9;
  20 2 = 400;
  2 20 = 1084576;
  20! = 2,432902 + 18 18 ;
• n = 10
  log (10) = 1;
  10 = 10;
  10 log (10) = 10;
  10 2 = 100;
  2 10 = 1024;
  10! = 3628800;

Performanța de rulare a unui algoritm este calculată în mod similar.

Iată câteva alte exemple algoritmice de analiză a timpului de rulare -

• Când vine vorba de căutare liniară, complexitatea timpului de rulare este O(n).
• Complexitatea timpului de rulare este O(log n) pentru căutarea binară.
• Pentru Sortare selecție, Sortare cu bule, Sortare cu găleată, Sortare prin inserție, complexitatea timpului de rulare este O(n^c).
• Când vine vorba de algoritmi exponențiali, cum ar fi Turnul din Hanoi, complexitatea timpului de rulare este O(c^n).
• Pentru Merge SortSort și Heap Sort, complexitatea timpului de rulare este O(n log n).

Cum analizează Big O complexitatea spațiului?

Determinarea complexității atât a spațiului cât și a timpului de rulare pentru un algoritm este un pas esențial. Acest lucru se datorează faptului că putem determina timpul de execuție pe care îl ia un algoritm analizând performanța de rulare a algoritmului și spațiul de memorie pe care îl ocupă algoritmul prin analiza complexității spațiale a algoritmului. Prin urmare, pentru a măsura complexitatea spațială a unui algoritm, trebuie să comparăm performanța în cel mai rău caz al complexității spațiale a algoritmului.

Pentru a determina complexitatea spațială a unui algoritm, trebuie să urmărim aceste două sarcini -

Sarcina 1: Este vital să implementați programul pentru un anumit algoritm.

Sarcina 2: Este esențial să cunoașteți dimensiunea intrării n pentru a determina memoria pe care o va deține fiecare articol.

Aceste două sarcini esențiale trebuie îndeplinite înainte de a calcula complexitatea spațiului pentru un algoritm.

Exemple de algoritmi de complexitate spațială

Există multe exemple de algoritmi cu complexitate spațială, dintre care unele au fost menționate mai jos pentru o mai bună înțelegere a acestui tip de algoritm:

• Pentru sortare cu bule, căutare liniară, sortare selecție, sortare inserție, sortare heap și căutare binară, complexitatea spațiului este O(1) .
• Complexitatea spațiului este O(n+k) când vine vorba de sortarea radix .
• Complexitatea spațiului este O(n) pentru SortSort rapid.
• Complexitatea spațiului este O(log n) pentru sortarea de îmbinare.

Exemplu de notație Big O în C

Este un fapt că notația Big O este folosită în primul rând în informatică pentru a determina complexitatea sau performanța unui algoritm. Această notație ne oferă capacitatea de a clasifica comportamentul algoritmilor pe baza creșterii spațiului de memorie sau a cerințelor de timp de execuție atunci când amploarea datelor de intrare devine mare. Nu este conceput pentru a prezice utilizarea reală a memoriei sau timpul de execuție, ci pentru a compara algoritmi și apoi a-i selecta pe cei mai buni dintre ei pentru lucrare. Nu este specific limbajului, dar este implementat și în C.

Mai jos, veți găsi algoritmul de sortare a selecției în C unde a fost calculată complexitatea în cel mai rău caz (notația Big O) a algoritmului:-

for(int i=0; i<n; i++)

{

int min = i;

for(int j=i; j<n; j++)

{

if(matrice[j]<matrice[min])

min=j;

}

int temp = matrice[i];

matrice[i] = matrice[min];

matrice[min] = temp;

}

Pentru a analiza algoritmul:

• Se poate nota deja că intervalul buclei for exterioare este i < n , ceea ce afirmă că ordinea buclei este O(n).
• În continuare, putem identifica că este și O(n) ca j < n pentru bucla for internă.
• Constanta este ignorată, chiar dacă randamentul mediu este găsit n/2 pentru o constantă c. Deci, ordinea este O(n).
• După înmulțirea ordinii buclei interioare și a buclei exterioare, complexitatea timpului de rulare atins este O(n^2).

Alți algoritmi în C pot fi ușor implementați, unde complexitățile pot fi ușor analizate și determinate în mod similar.

Utilizarea notării Big O

Există două domenii principale în care se aplică notația Big O: -

• Matematică : Notația Big O este destul de frecvent utilizată în domeniul matematicii pentru a descrie modul în care o serie finită aproximează îndeaproape o funcție, mai ales când vine vorba de cazurile unei expansiuni asimptotice sau ale unei serii Taylor trunchiate.
• Informatica: Este un fapt bine stabilit ca notatia Big O este folosita mai ales in domeniul informaticii datorita utilitatii sale in analiza algoritmilor.

Cu toate acestea, în ambele aplicații, funcția g ( x ) care apare în O (·) este adesea aleasă să fie cea mai simplă dacă termenii de ordin inferior și factorii constanți sunt omiși.

Există alte două utilizări ale acestei notații care sunt formal apropiate, dar relativ diferite. Sunt:-

• Asimptotice infinite
• Asimptotice infinitezimale.

Cu toate acestea, această distincție nu este în principiu, în aplicare doar cu definiția formală pentru „O mare” fiind exact aceeași pentru ambele cazuri. Singura diferență sunt limitele pentru argumentul funcției.

Citiți articolele noastre populare legate de dezvoltarea software

Concluzie

În concluzie, putem spune că Big Data joacă un rol esențial în structurile de date, iar a avea cunoștințe aprofundate și cuprinzătoare despre notația Big O este o abilitate excelentă de posedat. Este foarte solicitat în sectorul muncii și poate fi o alegere excelentă pentru o carieră. Programul de certificat avansat de la upGrad în Big Data vă va oferi pârghia de care aveți nevoie pentru a vă stimula cariera. Vă va prezenta abilități profesionale de top, cum ar fi Procesarea datelor cu PySpark, Data Warehousing, MapReduce, Big Data Processing pe AWS Cloud, Procesarea în timp real etc.