DAA - Metodologia di analisi

Per misurare il consumo di risorse di un algoritmo, vengono utilizzate diverse strategie come discusso in questo capitolo.

Analisi asintotica

Il comportamento asintotico di una funzione f(n) si riferisce alla crescita di f(n) come n diventa grande.

In genere ignoriamo valori piccoli di n, poiché di solito siamo interessati a stimare quanto sarà lento il programma su input di grandi dimensioni.

Una buona regola pratica è che più lento è il tasso di crescita asintotico, migliore è l'algoritmo. Anche se non è sempre vero.

Ad esempio, un algoritmo lineare $ f (n) = d * n + k $ è sempre asintoticamente migliore di uno quadratico, $ f (n) = cn ^ 2 + q $.

Risoluzione di equazioni di ricorrenza

Una ricorrenza è un'equazione o una disuguaglianza che descrive una funzione in termini di valore su input più piccoli. Le ricorrenze sono generalmente utilizzate nel paradigma divide et impera.

Lasciaci considerare T(n) essere il tempo di esecuzione su un problema di dimensioni n.

Se la dimensione del problema è abbastanza piccola, diciamo n < c dove c è una costante, la soluzione diretta richiede tempo costante, che è scritto come θ(1). Se la divisione del problema produce un numero di sottoproblemi con dimensione $ \ frac {n} {b} $.

Per risolvere il problema, il tempo necessario è a.T(n/b). Se consideriamo il tempo necessario per la divisione èD(n) e il tempo necessario per combinare i risultati dei sottoproblemi è C(n), la relazione di ricorrenza può essere rappresentata come -

$$ T (n) = \ begin {cases} \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \ theta (1) & if \: n \ leqslant c \\ a T (\ frac {n} {b}) + D (n) + C (n) e altrimenti \ end { casi} $$

Una relazione di ricorrenza può essere risolta utilizzando i seguenti metodi:

• Substitution Method - In questo metodo, indoviniamo un limite e usando l'induzione matematica dimostriamo che la nostra ipotesi era corretta.

• Recursion Tree Method - In questo metodo, viene formato un albero di ricorrenza in cui ogni nodo rappresenta il costo.

• Master’s Theorem - Questa è un'altra tecnica importante per trovare la complessità di una relazione di ricorrenza.

Analisi ammortizzata

L'analisi ammortizzata viene generalmente utilizzata per alcuni algoritmi in cui viene eseguita una sequenza di operazioni simili.

• L'analisi ammortizzata fornisce un limite al costo effettivo dell'intera sequenza, invece di limitare separatamente il costo della sequenza di operazioni.

• L'analisi ammortizzata differisce dall'analisi del caso medio; la probabilità non è coinvolta nell'analisi ammortizzata. L'analisi ammortizzata garantisce la performance media di ogni operazione nel caso peggiore.

Non è solo uno strumento di analisi, è un modo di pensare alla progettazione, poiché progettazione e analisi sono strettamente correlate.

Metodo aggregato

Il metodo aggregato fornisce una visione globale di un problema. In questo metodo, sen le operazioni richiedono il tempo peggiore T(n)in totale. Quindi il costo ammortizzato di ciascuna operazione èT(n)/n. Sebbene operazioni diverse possano richiedere tempi diversi, in questo metodo il costo variabile viene trascurato.

Metodo contabile

In questo metodo, addebiti diversi vengono assegnati a operazioni diverse in base al loro costo effettivo. Se il costo ammortizzato di un'operazione supera il suo costo effettivo, la differenza viene attribuita all'oggetto come credito. Questo credito aiuta a pagare per operazioni successive per le quali il costo ammortizzato è inferiore al costo effettivo.

Se il costo effettivo e il costo ammortizzato di i^th le operazioni sono $ c_ {i} $ e $ \ hat {c_ {l}} $, quindi

$$ \ displaystyle \ sum \ limits_ {i = 1} ^ n \ hat {c_ {l}} \ geqslant \ displaystyle \ sum \ limits_ {i = 1} ^ n c_ {i} $$

Metodo potenziale

Questo metodo rappresenta il lavoro prepagato come energia potenziale, invece di considerare il lavoro prepagato come credito. Questa energia può essere rilasciata per pagare le operazioni future.

Se ci esibiamo n operazioni che iniziano con una struttura dati iniziale D₀. Lasciaci considerare,c_i come il costo effettivo e D_i come struttura dati di i^thoperazione. La funzione potenziale Ф mappa su un numero reale Ф (D_i), il potenziale associato di D_i. Il costo ammortizzato $ \ hat {c_ {l}} $ può essere definito da

$$ \ hat {c_ {l}} = c_ {i} + \ Phi (D_ {i}) - \ Phi (D_ {i-1}) $$

Quindi, il costo ammortizzato totale è

$$ \ displaystyle \ sum \ limits_ {i = 1} ^ n \ hat {c_ {l}} = \ displaystyle \ sum \ limits_ {i = 1} ^ n (c_ {i} + \ Phi (D_ {i} ) - \ Phi (D_ {i-1})) = \ displaystyle \ sum \ limits_ {i = 1} ^ n c_ {i} + \ Phi (D_ {n}) - \ Phi (D_ {0}) $ $

Tabella dinamica

Se lo spazio allocato per la tabella non è sufficiente, dobbiamo copiare la tabella in una tabella di dimensioni maggiori. Allo stesso modo, se un numero elevato di membri viene cancellato dalla tabella, è una buona idea riallocare la tabella con una dimensione inferiore.

Utilizzando l'analisi ammortizzata, possiamo mostrare che il costo ammortizzato di inserimento e cancellazione è costante e lo spazio inutilizzato in una tabella dinamica non supera mai una frazione costante dello spazio totale.

Nel prossimo capitolo di questo tutorial, discuteremo brevemente delle notazioni asintotiche.