Strutture dati - Analisi asintotica

L'analisi asintotica di un algoritmo si riferisce alla definizione del limite / inquadramento matematico delle sue prestazioni in fase di esecuzione. Utilizzando l'analisi asintotica, possiamo benissimo concludere il caso migliore, il caso medio e lo scenario peggiore di un algoritmo.

L'analisi asintotica è vincolata all'input, cioè, se non c'è input all'algoritmo, si conclude che funziona in un tempo costante. Oltre all '"input" tutti gli altri fattori sono considerati costanti.

L'analisi asintotica si riferisce al calcolo del tempo di esecuzione di qualsiasi operazione in unità matematiche di calcolo. Ad esempio, il tempo di esecuzione di un'operazione viene calcolato come f (n) e può essere calcolato come g (n 2 ) per un'altra operazione . Ciò significa che il tempo di esecuzione della prima operazione aumenterà linearmente con l'aumento din e il tempo di esecuzione della seconda operazione aumenterà esponenzialmente quando naumenta. Allo stesso modo, il tempo di esecuzione di entrambe le operazioni sarà quasi lo stesso sen è significativamente piccolo.

Di solito, il tempo richiesto da un algoritmo rientra in tre tipi:

  • Best Case - Tempo minimo richiesto per l'esecuzione del programma.

  • Average Case - Tempo medio richiesto per l'esecuzione del programma.

  • Worst Case - Tempo massimo richiesto per l'esecuzione del programma.

Notazioni asintotiche

Di seguito sono riportate le notazioni asintotiche comunemente utilizzate per calcolare la complessità del tempo di esecuzione di un algoritmo.

  • Ο Notazione
  • Notazione Ω
  • θ Notazione

Notazione Big Oh, Ο

La notazione Ο (n) è il modo formale per esprimere il limite superiore del tempo di esecuzione di un algoritmo. Misura la complessità temporale del caso peggiore o il tempo più lungo che un algoritmo può impiegare per essere completato.

Ad esempio, per una funzione f(n)

Ο(f(n)) = { g(n) : there exists c > 0 and n0 such that f(n) ≤ c.g(n) for all n > n0. }

Notazione Omega, Ω

La notazione Ω (n) è il modo formale per esprimere il limite inferiore del tempo di esecuzione di un algoritmo. Misura la migliore complessità temporale del caso o la migliore quantità di tempo che un algoritmo può impiegare per completare.

Ad esempio, per una funzione f(n)

Ω(f(n)) ≥ { g(n) : there exists c > 0 and n0 such that g(n) ≤ c.f(n) for all n > n0. }

Notazione Theta, θ

La notazione θ (n) è il modo formale per esprimere sia il limite inferiore sia il limite superiore del tempo di esecuzione di un algoritmo. È rappresentato come segue:

θ(f(n)) = { g(n) if and only if g(n) =  Ο(f(n)) and g(n) = Ω(f(n)) for all n > n0. }

Notazioni asintotiche comuni

Di seguito è riportato un elenco di alcune notazioni asintotiche comuni:

costante - Ο (1)
logaritmico - Ο (log n)
lineare - Ο (n)
n log n - Ο (n log n)
quadratico - Ο (n 2 )
cubo - Ο (n 3 )
polinomio - n Ο (1)
esponenziale - 2 Ο (n)