differenza tra metodi contabili e potenziali nell'Analisi Ammortizzata

Question

differenza tra metodi contabili e potenziali nell'Analisi Ammortizzata

#1 da (4 voti)
#2 da (1 voti)

6

Stavo passando per l'Introduzione agli algoritmi di Cormen et al.Nel capitolo intitolato Amortized Analysis, la differenza tra metodi contabili e potenziali è data in questo modo

The accounting method overcharges some operations early in the sequence, storing the overcharge as “prepaid credit” on specific objects in the data structure. ...

The potential method maintains the credit as the “potential energy” of the data structure as a whole instead of associating the credit with individual objects within the data structure.

Ho cercato di capire questo usando l'esempio di array ridimensionabile che raddoppia le sue dimensioni quando non c'è spazio per inserire un elemento. Quello che non riuscivo a capire era la seguente frase

storing the overcharge as “prepaid credit” on specific objects in the data structure

Utilizzo del metodo Contabilità:

ci = l'addebito per l'operazione i-esimo

c'i = costo ammortizzato dell'operazione i-esimo

Si = dimensione dell'array dopo l'operazione i-esima

bi = saldo del credito dopo l'operazione i-esima

i   1  2  3  4  5  6  7  8  9 10
si  1  2  4  4  8  8  8  8 16 16
ci  1  2  3  1  5  1  1  1  9  1
c'i 3  3  3  3  3  3  3  3  3  3
bi  2  3  3  5  3  5  7  9  3  5

che cosa significa esattamente "memorizzare su oggetti specifici nella struttura dati" significa qui?

Nel metodo potenziale, se uso phi per essere 2n-m dove n = numero di elementi currebt nella matrice, e m = dimensione dell'array

                n     m    phi
empty            0     0    0 
add first elem   1     1    1
add secondelem   2     2    2
add third elem   3     4    2
add fourth elem  4     4    4
add fifth  elem  5     8    2

In questo, cosa significa "... la" energia potenziale "della struttura dati nel suo insieme invece di associare il credito con singoli oggetti all'interno della struttura dati."

algorithms algorithm-analysis

posta damon 15.08.2013 - 14:50

fonte

2 risposte

1

Il modo più semplice per comprendere l'analisi del caso peggiore ammortizzata è considerarlo come la media delle prestazioni peggiori in una lunga sequenza di chiamate. Una chiamata specifica può avere risultati significativamente peggiori o significativamente migliori rispetto al valore, ma la media di tutte le chiamate effettuate è deterministicamente che si avvicina a tale valore.

risposta data 16.08.2013 - 03:56

fonte

Leggi altre domande sui tag algorithms algorithm-analysis

Una nuova libreria i / o: una buona idea o una veramente buona? Quale livello introdurre messaggi di errore leggibili dall'uomo?

score 4 · Accepted Answer

Metodo di contabilità:

Il metodo di contabilità funziona per determinare un pagamento di alcune unità di tempo supplementari addebitate a ciascuna singola operazione in modo che la somma di tutti i pagamenti non sia superata dal costo totale effettivo.

Puoi pensarci su come un conto in banca dove addebiti un po 'di più del costo effettivo per ogni conto bancario in un pool in modo che operazioni molto costose possano essere addebitate meno del loro costo effettivo, pagato dal pool di risparmio. Questo espande le operazioni ad alto costo sull'intera sequenza.

Le tariffe per ogni operazione devono essere abbastanza grandi da mantenere il saldo nel conto positivo pur essendo abbastanza piccolo da non sovraccaricare significativamente l'operazione al di sopra del suo costo effettivo.

Question: Help understand this:
storing the overcharge as “prepaid credit” on specific objects in the data structure

Answer:
Given:
  Cost to insert is 1
  Cost to move each value when table is doubled is 1
  Charge for each insert is 3

Insert #1:
cost = 1 (insert: 1)
charge = 3
bankedAmount= 2
bankBalance = 2
NOTE: The bankedAmount is associated with this transaction, but then just put into the account -- that is the prepaid credit due to specific object in the data structure.

Insert #2:
cost = 2 (doubleTableAndMove: 1*1 = 1, insert: 1)
charge = 3
bankedAmount= 1
bankBalance = 3

Insert #3:
cost = 3 (doubleTableAndMove: 2*1 = 2, insert: 1)
charge = 3
bankedAmount= 0
bankBalance = 3

Insert #4:
cost = 1 (insert: 1)
charge = 3
bankedAmount= 2
bankBalance = 5

Insert #5:
cost = 5 (doubleTableAndMove: 4*1 = 4, insert: 1)
charge = 3
bankedAmount= -2
bankBalance = 3

etc...

Metodo potenziale:

Question: In this ,what does it mean by "...the “potential energy” of the data structure as a whole instead of associating the credit with individual objects within the data structure."

Answer: Its analogous to the bank account concept in the accounting method. The potential function keeps track of the total extra time charged at any time in a sequence of operations, but it's only based on the current state of the structure, regardless of all the operations that put it into that state.

C'è un'ulteriore spiegazione con maggiori dettagli qui .