Grande o notazione nella struttura dei dati: tutto da sapere

La notazione Big O in una struttura dati viene utilizzata per determinare l'efficienza di un algoritmo, la quantità di tempo necessaria per eseguire la funzione con la crescita dell'input e la scalabilità della funzione. La misurazione di questa efficienza può essere suddivisa in due parti, vale a dire, complessità spaziale e complessità temporale.

La notazione Big O si riferisce alla notazione matematica che funge da fattore limitante di qualsiasi funzione quando un argomento è più incline a inclinarsi verso un valore specifico o infinito. Appartiene alla categoria delle notazioni matematiche inventate da Edmund Landau, Paul Bachmann e altri. Quindi, è chiamata collettivamente notazione Bachmann-Landau o notazione asintotica.

Secondo la deduzione matematica, due funzioni, f(n) e g(n) sono definite su un insieme di numeri positivi o reali che non sono vincolati. Qui g(n) è strettamente positivo per ogni grande valore di n. Può essere scritto nel modo seguente:

f(n) = O(g(n)) in cui n tende all'infinito (n → ∞)

Tuttavia, qui, la supposizione di n all'infinito non è definita esclusivamente e l'espressione di cui sopra può quindi essere scritta come:

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

Qui, f e g sono le funzioni necessarie che partono da numeri interi positivi a numeri reali che non sono negativi.

Quindi, valori n grandi sono indicati dal Big O asintotico.

Proprietà della notazione Big O nella struttura dei dati

L' algoritmo Big O nella struttura dei dati ha alcune proprietà obbligatorie. Le suddette proprietà essenziali della notazione Big O sono le seguenti:

• Funzione di somma:
  Se f(n) = f 1 (n) + f 2 (n) + — + f m (n) e f io (n)≤ f i +1(n) ∀ i=1, 2,–, m,
  quindi O(f(n)) = O(max(f1(n), f2(n), –, fm(n))).
• Funzione logaritmica:
  Se f(n) = logan e g(n)=logbn,
  quindi O(f(n))=O(g(n))
• Moltiplicazione costante:
  Se f(n) = cg(n), allora O(f(n)) = O(g(n)) in cui c è una costante diversa da zero.
• Funzione polinomiale:
  Se f(n) = a0 + a1.n + a2.n2 + — + am.nm,
  quindi O(f(n)) = O(nm).

Impara i corsi di sviluppo software online dalle migliori università del mondo. Guadagna programmi Executive PG, programmi di certificazione avanzati o programmi di master per accelerare la tua carriera.

Esplora i nostri corsi di ingegneria del software popolari

Qui, mentre si indirizza Big O, ogni singola funzione di registro aumenta in modo simile.

Importanza della notazione Big O nell'analisi di runtime degli algoritmi

Le complessità del tempo di esecuzione nel caso peggiore dell'algoritmo vengono utilizzate per effettuare confronti e calcolare, soprattutto nel caso di analisi delle prestazioni di un algoritmo. L'ordine di O(1), rappresentato come il tempo di esecuzione costante, è il tempo di esecuzione più veloce dell'algoritmo: il tempo impiegato dall'algoritmo è lo stesso per varie dimensioni di input. È importante notare che il tempo di esecuzione ideale di un algoritmo è il tempo di esecuzione costante, che viene raggiunto molto raramente perché il tempo di esecuzione dell'algoritmo dipende dalla dimensione dell'input di n.

Per esempio:

Come accennato in precedenza, le prestazioni di runtime di un algoritmo dipendono principalmente dalla dimensione dell'input di n. Spieghiamo questo fatto con alcuni esempi matematici per effettuare l'analisi di runtime di un algoritmo per varie dimensioni di 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;

Le prestazioni di runtime di un algoritmo vengono calcolate in modo simile.

Ecco alcuni altri esempi algoritmici di analisi di runtime:

• Quando si tratta di ricerca lineare, la complessità del runtime è O(n).
• La complessità del runtime è O(log n) per la ricerca binaria.
• Per l'ordinamento per selezione, l'ordinamento a bolle, l'ordinamento per secchio, l'ordinamento per inserimento, la complessità del runtime è O(n^c).
• Quando si tratta di algoritmi esponenziali come la Torre di Hanoi, la complessità del runtime è O(c^n).
• Per Merge SortSort e Heap Sort, la complessità di runtime è O(n log n).

In che modo Big O analizza la complessità dello spazio?

Determinare sia la complessità dello spazio che quella del runtime per un algoritmo è un passaggio essenziale. Questo perché possiamo determinare il tempo di esecuzione impiegato da un algoritmo analizzando le prestazioni di runtime dell'algoritmo e lo spazio di memoria che l'algoritmo sta occupando attraverso l'analisi della complessità spaziale dell'algoritmo. Pertanto, per misurare la complessità spaziale di un algoritmo, dobbiamo confrontare le prestazioni di complessità spaziale dell'algoritmo nel caso peggiore.

Per determinare la complessità spaziale di un algoritmo, dobbiamo seguire questi due compiti:

Compito 1: è fondamentale implementare il programma per un particolare algoritmo.

Compito 2: è essenziale conoscere la dimensione dell'input n per determinare la memoria che ogni elemento conterrà.

Questi due compiti essenziali devono essere eseguiti prima di calcolare la complessità dello spazio per un algoritmo.

Esempi di algoritmi di complessità spaziale

Esistono molti esempi di algoritmi con complessità spaziale, alcuni dei quali sono stati menzionati di seguito per una migliore comprensione di questo tipo di algoritmo:

• Per Ordinamento a bolle, Ricerca lineare, Ordinamento per selezione, Ordinamento per inserimento, Ordinamento per heap e Ricerca binaria, la complessità dello spazio è O(1) .
• La complessità dello spazio è O(n+k) quando si tratta di radix sort .
• La complessità dello spazio è O(n) per SortSort rapido.
• La complessità dello spazio è O(log n) per merge sort.

Esempio di notazione O grande in C

È un dato di fatto che la notazione Big O viene utilizzata principalmente in informatica per determinare la complessità o le prestazioni di un algoritmo. Questa notazione ci fornisce la possibilità di classificare il comportamento degli algoritmi in base alla crescita dello spazio di memoria o ai requisiti di tempo di esecuzione quando l'estensione dei dati di input diventa grande. Non è progettato per prevedere l'utilizzo effettivo della memoria o il tempo di esecuzione, ma per confrontare gli algoritmi e quindi selezionare i migliori per il lavoro. Non è specifico della lingua, ma è implementato anche in C.

Di seguito, troverai l'algoritmo di ordinamento della selezione in C in cui è stata calcolata la complessità del caso peggiore (notazione Big O) dell'algoritmo: -

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

{

int min = i;

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

{

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

min=j;

}

int temp = matrice[i];

matrice[i] = matrice[min];

matrice[min] = temperatura;

}

Per analizzare l'algoritmo:

• Si può già denotare che l'intervallo del ciclo for esterno è i < n , il che afferma che l'ordine del ciclo è O(n).
• Successivamente, possiamo identificare che è anche O(n) come j < n per il ciclo for interno.
• La costante viene ignorata, anche se l'efficienza media viene trovata n/2 per una costante c. Quindi, l'ordine è O(n).
• Dopo aver moltiplicato l'ordine del ciclo interno e del ciclo esterno, la complessità di runtime ottenuta è O(n^2).

Altri algoritmi in C possono essere facilmente implementati, dove le complessità possono essere facilmente analizzate e determinate in modo simile.

Uso della notazione O grande

Ci sono due aree principali in cui viene applicata la notazione Big O: -

• Matematica : la notazione O grande è abbastanza comunemente usata nel campo della matematica per descrivere come una serie finita approssima da vicino una funzione, specialmente quando si tratta di casi di espansione asintotica o serie di Taylor troncata.
• Informatica: è un fatto assodato che la notazione Big O è utilizzata principalmente nel campo dell'informatica per la sua utilità nell'analisi di algoritmi

Tuttavia, in entrambe le applicazioni, la funzione g ( x ) che appare all'interno di O (·) viene spesso scelta come forse la più semplice se si omettono termini di ordine inferiore e fattori costanti.

Ci sono altri due usi di questa notazione che sono formalmente vicini ma relativamente diversi. Sono:-

• Asintotici infiniti
• Asintotici infinitesimali.

Tuttavia, questa distinzione non è in linea di principio, applicabile solo con la definizione formale di "Big O" che è esattamente la stessa per entrambi i casi. L'unica differenza sono i limiti per l'argomento della funzione.

Leggi i nostri articoli popolari relativi allo sviluppo software

Conclusione

In conclusione, possiamo dire che i Big Data svolgono un ruolo fondamentale nelle strutture dei dati e avere una conoscenza approfondita e completa della notazione Big O è un eccellente set di abilità da possedere. È molto richiesto nel settore del lavoro e può essere potenzialmente un'ottima scelta per un percorso professionale. Il programma di certificazione avanzata di upGrad in Big Data ti darà la leva di cui hai bisogno per dare impulso alla tua carriera. Ti introdurrà alle migliori competenze professionali come Elaborazione dati con PySpark, Data Warehousing, MapReduce, Elaborazione Big Data sul cloud AWS, Elaborazione in tempo reale, ecc.