Analisi ammortizzata
18
1/18 Analisi ammortizzata
description
Analisi ammortizzata. Analisi Ammortizzata. Nell’analisi ammortizzata si vuole definire il costo computazionale di una sequenza di n operazioni. Il tempo di esecuzione di una sequenza di operazioni è definito come la media dei tempi di esecuzione delle operazioni della sequenza. - PowerPoint PPT Presentation
Transcript of Analisi ammortizzata
1/18
Analisi ammortizzata
2/18
Analisi Ammortizzata
Nell’analisi ammortizzata si vuole definire il costo computazionale di una sequenza di n operazioni.
Il tempo di esecuzione di una sequenza di operazioni è definito come la media dei tempi di esecuzione delle operazioni della sequenza.Si considera l’efficienza nel caso pessimo di ciascuna operazione, in cui tipicamente qualche operazione è molto costosa.Se le operazioni costose avvengono di rado, il costo medio della sequenza è più basso di quando derivato dalla somma dei casi pessimi.
3/18
Analisi ammortizzata
NON è un’analisi del caso medio. Non si considerano distribuzioni di probabilità. Si analizza l’efficienza media di ogni operazione nel caso pessimo.Tre metodi:•Metodo degli aggregati•Metodo degli accantonamenti•Metodo del potenzialeDue esempi:•Pila con multipop•Contatore binario
4/18
Esempio 1: Pila con multipop
Pila con una operazione addizionale: multipop(S,k), che rimuove i primi k elementi in testa alla pila S.Multipop(S,k)
while not(Stack-Empty(S)) and k0 do Pop(S)
k=k-1
Push e pop sono eseguite in O(1)multipop richiede O(n) nel caso pessimo.Una sequenza di n operazioni sulla pila ha quindi tempo nel caso pessimo O(n2).
5/18
Esempio 1: Pila con multipop
La stima O(n2) è iniqua: ogni elemento può essere tolto solo dopo essere stato inserito.Il costo dei pop, multi o singoli, non può superare il costo dei push.Dato che push costa O(1), intuitivamente il costo di n operazioni deve essere O(n), anche nel caso pessimo.
6/18
Esempio 2: incremento di contatore binario
Contatore binario di k bit, array A[0 … k-1], con A[0] LSB.Per sommare 1 modulo 2k al valore corrente:Increment(A)i=0while i<length[A] and A[i]==1 do A[i]=0 i=i+1if i<length[A] then A[i]=1Caso pessimo: tutti elementi a 1, tempo (k).n operazioni increment, tempo O(nk).
7/18
Esempio 2: incremento di contatore binario
La stima O(nk) è iniqua: non tutte le volte si complementa un bit terminale di una stringa di tutti 1.A[0] viene complementato ad ogni chiamata di insert.A[1] viene complementato n/2 volte. A[2] viene complementato n/4 volte.…A[i] viene complementato n/2i volte.
8/18
Il metodo degli aggregati
Lo si utilizza per dimostrare che, per tutti i valori di n, una sequenza di n operazioni richiede nel caso pessimo tempo T(n).Quindi nel caso pessimo il costo ammortizzato, costo medio di ogni operazione è T(n)/n.E’ un metodo meno preciso degli altri due, dato che dà ad ogni operazione lo stesso costo.
9/18
Il metodo degli aggregati: esempio pila
Push e pop costano O(1)Multipop costa O(n)Pop e multipop possono solo togliere elementi precedentemente inseriti da push.In n operazioni al massimo posso inserire n elementi.Una sequenza di n operazioni (push, pop e multipop) richiede un tempo totale O(n).Il costo ammortizzato di ogni operazione è O(n)/n = O(1).
10/18
Il metodo degli aggregati: es. contatore
A seguito di n operazioni di incremento (modulo n), ogni i-esimo bit viene modificato n/2i volte.Il numero totale di operazioni di modifica è
Quindi nel caso pessimo il costo di n incrementi è O(n).Il costo ammortizzato di ogni singola operazione è O(1).
ni
ii
i nn 22/12/0
n lg
0
11/18
Il metodo degli accantonamenti
Si assegna un valore (inventato) diverso ad ogni operazione: il valore è il costo ammortizzato.Una operazione i effettuata su un dato cui è assegnato un valore maggiore del suo costo ci genera un credito associato al dato.
Altre operazioni sullo stesso dato potranno poi pagare il loro costo con il credito associato al dato.I crediti non possono mai diventare negativi.La somma dei costi ammortizzati per una sequenza di operazioni è un upper bound costo totale effettivo di quelle operazioni.
12/18
Il metodo degli accantonamenti: es. pila
Costi ammortizzati:2 per push0 per pop e multipop.NOTA: il costo ammortizzato di ogni operazione è O(1).Le due unità guadagnate ad ogni push sono usate così:• 1 unità per pagare il costo del push.• 1 unità a credito per pagare i pop futuri.Togliere un elemento costa 1, per poterlo togliere bisogna prima averlo messo.Una sequenza di n operazioni push, pop e multipop, ha un costo ammortizzato di O(n), e questo è un upper bound al costo effettivo.
13/18
Il metodo degli accantonamenti: es. contatore
Costo ammortizzato di 2 per ogni operazione di bit a 1.Quando si vuole mettere un bit a 1 si paga 1 e si accantona 1 a credito su quel bit.Il credito viene usato quando si vuole mettere a 0 quel bit.Per potersi pagare un passaggio di un bit a 0, bisogna prima averlo messo a 1.Ogni chiamata di increment porta a 1 un solo bit della stringa.Il numero di 1 nella stringa non è mai negativo (credito sempre positivo).Una sequenza di n increment ha costo ammortizzato O(n).
14/18
Il metodo del potenziale
Questo metodo paga in anticipo il lavoro definendo un potenziale utilizzabile per pagare operazioni future.Il potenziale è associato all’intera struttura dati, non ad elementi specifici.
Notazione:• Do struttura dati iniziale
• Di struttura dati dopo la iesima operazione
• ci costo effettivo della iesima operazione.
• la funzione potenziale associa alla struttura dati Di il suo valore di potenziale (Di).
15/18
Il metodo del potenziale
Analisi ammortizzataIl costo ammortizzato c* della iesima operazione è definito da
Quindi c* = costo effettivo + variazione di potenzialeIl costo ammortizzato totale diventa
Richiedendo chePer ogni i, ci si assicura che il costo ammortizzato totale sia un upper bound al costo effettivo di ogni sequenza di n operazioni.
)()( 1*
iiii DDcc
)()( 0* DDcc ni ii i
0)()( 0 DDi
16/18
Il metodo del potenziale
Di solito (D0)=0 e (Di)0 per ogni i.
Se (Di) - (Di-1) > 0 si ha un versamento, il potenziale cresce.Altrimenti un prelievo, il potenziale cala.
17/18
Il metodo del poteziale: es. pila
Inizialmente la struttura dati D è una pila vuota.Definendo (D) come il numero di elementi nella pila, si ha:(D0) = 0 e (Di) 0 per ogni iPUSH: se l’iesima operazione su D è un push:(Di) - (Di-1) = (Di-1) +1 - (Di-1) = 1Il costo ammortizzato di un push è:ci* = ci + [(Di) - (Di-1)] = 1 + 1 = 2MULTIPOP: se l’iesima operazione su D è un multipop(D,k) e k' = min{|D|,k}:ci = k'eci* = ci + [(Di) - (Di-1)] = k' - k' = 0POP: se l’iesima operazione su D è un pop, si ha ci* = 0Costi:• Il costo ammortizzato di ogni operazione è O(1).• Il costo ammortizzato di n operazioni è O(n).• L’upper bound al costo totale è O(n).
18/18
Il metodo del poteziale: es. contatore
Si definisce il potenziale del contatore dopo l’iesima operazione di incremento come bi, numero di bit a 1.Se la iesima operazione porta a zero ti bit, il costo è al più ti+1 e bibi-1-ti+1.
Quindi(Di)-(Di-1) (bi-1-ti+1) - bi-1 = 1 – ti
Costo ammortizzato:ci*= ci+ (Di)-(Di-1) (ti+1)+(1 – ti)=2
Quindi il costo di n operazioni di incremento nel caso pessimo è O(n).
