Notazioni asintotiche e analisi Apriori
Nella progettazione di algoritmi, l'analisi della complessità di un algoritmo è un aspetto essenziale. Principalmente, la complessità algoritmica riguarda le sue prestazioni, quanto velocemente o lentamente funzioni.
La complessità di un algoritmo descrive l'efficienza dell'algoritmo in termini di quantità di memoria richiesta per elaborare i dati e il tempo di elaborazione.
La complessità di un algoritmo viene analizzata in due prospettive: Time e Space.
Complessità temporale
È una funzione che descrive la quantità di tempo richiesta per eseguire un algoritmo in termini di dimensione dell'input. "Tempo" può significare il numero di accessi alla memoria effettuati, il numero di confronti tra interi, il numero di volte in cui viene eseguito un ciclo interno o qualche altra unità naturale correlata alla quantità di tempo reale che l'algoritmo impiegherà.
Complessità spaziale
È una funzione che descrive la quantità di memoria che un algoritmo richiede in termini di dimensione dell'input dell'algoritmo. Si parla spesso di memoria "extra" necessaria, senza contare la memoria necessaria per memorizzare l'input stesso. Ancora una volta, usiamo unità naturali (ma di lunghezza fissa) per misurarlo.
La complessità dello spazio a volte viene ignorata perché lo spazio utilizzato è minimo e / o ovvio, tuttavia a volte diventa un problema importante quanto il tempo.
Notazioni asintotiche
Il tempo di esecuzione di un algoritmo dipende dal set di istruzioni, dalla velocità del processore, dalla velocità di I / O del disco, ecc. Pertanto, stimiamo l'efficienza di un algoritmo in modo asintotico.
La funzione temporale di un algoritmo è rappresentata da T(n), dove n è la dimensione dell'input.
Diversi tipi di notazioni asintotiche vengono utilizzati per rappresentare la complessità di un algoritmo. Le seguenti notazioni asintotiche vengono utilizzate per calcolare la complessità del tempo di esecuzione di un algoritmo.
O - Grande Oh
Ω - Big omega
θ - Grande theta
o - Piccolo Oh
ω - Un po 'di omega
O: limite superiore asintotico
'O' (Big Oh) è la notazione più comunemente usata. Una funzionef(n) può essere rappresentato è l'ordine di g(n) questo è O(g(n)), se esiste un valore intero positivo n come n0 e una costante positiva c tale che -
$ f (n) \ leqslant cg (n) $ per $ n> n_ {0} $ in tutti i casi
Quindi, funzione g(n) è un limite superiore per la funzione f(n), come g(n) cresce più velocemente di f(n).
Esempio
Consideriamo una data funzione, $ f (n) = 4.n ^ 3 + 10.n ^ 2 + 5.n + 1 $
Considerando $ g (n) = n ^ 3 $,
$ f (n) \ leqslant 5.g (n) $ per tutti i valori di $ n> 2 $
Quindi, la complessità di f(n) può essere rappresentato come $ O (g (n)) $, cioè $ O (n ^ 3) $
Ω: limite inferiore asintotico
Diciamo che $ f (n) = \ Omega (g (n)) $ quando esiste una costante c che $ f (n) \ geqslant cg (n) $ per tutti i valori sufficientemente grandi di n. Quinè un numero intero positivo. Significa funzioneg è un limite inferiore per la funzione f; dopo un certo valore din, f non andrà mai sotto g.
Esempio
Consideriamo una data funzione, $ f (n) = 4.n ^ 3 + 10.n ^ 2 + 5.n + 1 $.
Considerando $ g (n) = n ^ 3 $, $ f (n) \ geqslant 4.g (n) $ per tutti i valori di $ n> 0 $.
Quindi, la complessità di f(n) può essere rappresentato come $ \ Omega (g (n)) $, ovvero $ \ Omega (n ^ 3) $
θ: Asintotico Tight Bound
Diciamo che $ f (n) = \ theta (g (n)) $ quando esistono delle costanti c1 e c2 che $ c_ {1} .g (n) \ leqslant f (n) \ leqslant c_ {2} .g (n) $ per tutti i valori sufficientemente grandi di n. Quin è un numero intero positivo.
Questo significa funzione g è un limite stretto per la funzione f.
Esempio
Consideriamo una data funzione, $ f (n) = 4.n ^ 3 + 10.n ^ 2 + 5.n + 1 $
Considerando $ g (n) = n ^ 3 $, $ 4.g (n) \ leqslant f (n) \ leqslant 5.g (n) $ per tutti i valori grandi di n.
Quindi, la complessità di f(n) può essere rappresentato come $ \ theta (g (n)) $, cioè $ \ theta (n ^ 3) $.
O - Notazione
Il limite superiore asintotico fornito da O-notationpuò o non può essere asintoticamente stretto. Il limite $ 2.n ^ 2 = O (n ^ 2) $ è asintoticamente stretto, ma il limite $ 2.n = O (n ^ 2) $ non lo è.
Noi usiamo o-notation per denotare un limite superiore che non è asintoticamente stretto.
Definiamo formalmente o(g(n)) (little-oh of g of n) come l'insieme f(n) = o(g(n)) per ogni costante positiva $ c> 0 $ ed esiste un valore $ n_ {0}> 0 $, tale che $ 0 \ leqslant f (n) \ leqslant cg (n) $.
Intuitivamente, in o-notation, la funzione f(n) diventa insignificante rispetto a g(n) come nsi avvicina all'infinito; questo è,
$$ \ lim_ {n \ rightarrow \ infty} \ left (\ frac {f (n)} {g (n)} \ right) = 0 $$
Esempio
Consideriamo la stessa funzione, $ f (n) = 4.n ^ 3 + 10.n ^ 2 + 5.n + 1 $
Considerando $ g (n) = n ^ {4} $,
$$ \ lim_ {n \ rightarrow \ infty} \ left (\ frac {4.n ^ 3 + 10.n ^ 2 + 5.n + 1} {n ^ 4} \ right) = 0 $$
Quindi, la complessità di f(n) può essere rappresentato come $ o (g (n)) $, cioè $ o (n ^ 4) $.
ω - Notazione
Noi usiamo ω-notationper denotare un limite inferiore che non è asintoticamente stretto. Formalmente, tuttavia, definiamoω(g(n)) (little-omega of g of n) as the set f(n) = ω(g(n)) per qualsiasi costante positiva C > 0 ed esiste un valore $ n_ {0}> 0 $, tale che $ 0 \ leqslant cg (n) <f (n) $.
Ad esempio, $ \ frac {n ^ 2} {2} = \ omega (n) $, ma $ \ frac {n ^ 2} {2} \ neq \ omega (n ^ 2) $. La relazione $ f (n) = \ omega (g (n)) $ implica che esista il seguente limite
$$ \ lim_ {n \ rightarrow \ infty} \ left (\ frac {f (n)} {g (n)} \ right) = \ infty $$
Questo è, f(n) diventa arbitrariamente grande rispetto a g(n) come n si avvicina all'infinito.
Esempio
Consideriamo la stessa funzione, $ f (n) = 4.n ^ 3 + 10.n ^ 2 + 5.n + 1 $
Considerando $ g (n) = n ^ 2 $,
$$ \ lim_ {n \ rightarrow \ infty} \ left (\ frac {4.n ^ 3 + 10.n ^ 2 + 5.n + 1} {n ^ 2} \ right) = \ infty $$
Quindi, la complessità di f(n) può essere rappresentato come $ o (g (n)) $, cioè $ \ omega (n ^ 2) $.
Analisi Apriori e Apostiari
Analisi Apriori significa che l'analisi viene eseguita prima di eseguirla su un sistema specifico. Questa analisi è una fase in cui una funzione viene definita utilizzando un modello teorico. Quindi, determiniamo la complessità temporale e spaziale di un algoritmo semplicemente osservando l'algoritmo anziché eseguirlo su un particolare sistema con una memoria, un processore e un compilatore diversi.
Analisi apostiari di un algoritmo significa che eseguiamo l'analisi di un algoritmo solo dopo averlo eseguito su un sistema. Dipende direttamente dal sistema e cambia da sistema a sistema.
In un settore non possiamo eseguire analisi Apostiari in quanto il software è generalmente realizzato per un utente anonimo, che lo esegue su un sistema diverso da quelli presenti nel settore.
In Apriori, è il motivo per cui usiamo notazioni asintotiche per determinare la complessità temporale e spaziale mentre cambiano da computer a computer; tuttavia, asintoticamente sono gli stessi.