Stack Multipop

Stack con Multipop

Abbiamo tre operazioni:

Definiamo la procedura di :

Multipop(S,k)
while not STACK_EMPTY(s) and k>0 do:
	POP(s)
	k--

Analisi di una sequenza di operazioni su uno stack inizialmente vuoto.

• Costo di una singola operazione
• Costo di operazioni Questa è una sovrastimazione del costo effettivo che potremmo ottenere.

Lo Stack è inizialmente vuoto a meno che non venga specificato altrimenti

Multipop con Aggregazione

Le operazioni di Pop e Push sono elementari, mentre MultiPop(S,k) è un’operazione composta (da più pop). Sia una qualsiasi operazione (pop, push, multipop):

{Pop, Push, Multipop} {Pop, Push}

Ossia abbiamo ora operazioni elementari. Ogni multipop è stata scomposta in una sequenza di pop semplici.

Costo = costo =

Cioè abbiamo fatto:

Per questo cambia l’indice da n ad m. significa che multipop esegue per volte, oppure fino a svuotamento totale dello stack.

Multipop \to Sequenza di Pop

Upper Bound numero Pop

Il numero delle pop può al più essere il numero delle push effettuate nello stack.

Cioè il numero di push non varia nella semplificazione di multipop in sequenze di pop.

Pertanto

Da cui troviamo il costo :

Esempio di sequenza peggiore

Multipop con Accantonamenti

Assegneremo un costo più alto all’operazione di . 

Poniamo: 

(1 unità per il costo reale, + 1 unità per il costo ammortizzato da noi assegnato);  

 

In ogni istante avremo: dove |S| è il numero di elementi nello stack. 

e quindi:  

Avendo assegnato 2 al costo ammortizzato dell’operazione , avremo: 

Controesempio:

Se avessimo assegnato costi ammortizzati inversi, una sequenza di sole push senza mai eseguire pop avrebbe generato credito negativo.

Multipop con Potenziale

Poniamo , con lo Stack vuoto. Poniamo, come da teoria, , quindi siamo sicuri che . 

Vogliamo trovare valori costanti nei costi ammortizzati.

 

•  
  • in quanto:
• • in quanto
• • in quanto:   Abbiamo trovato gli stessi valori degli altri metodi: . 

Questa è una manifestazione della Proprietà di Confluenza: i crediti non dipendono dalla sequenza, ma dalla struttura dati.

Stack inizialmente non vuoto

Se lo stack non è vuoto, purché non sia enorme, le sue operazioni rimangono lineari.

Se