Confusione nella comprensione del teorema sull'ammortamento

2

Stavo leggendo un libro su Algorithm Analysis di Micheal T Goodrich. Mi sono imbattuto in una tecnica di ammortamento e sono rimasto colpito nel comprendere la dimostrazione del teorema. Sto mettendo il teorema e la dimostrazione e la parte che mi serve ancora qualche spiegazione. Per favore aiutami:

Teorema: una serie di operazioni n su una tabella vuota inizialmente implementata con un array richiede O (n) tempo

Definizione della tabella clearable: questo tipo di dati Abstract memorizza la tabella degli elementi, a cui è possibile accedere tramite il loro indice nella tabella. Inoltre, questo ADT supporta i seguenti due metodi:

add(e): Add the element e to the next available cell in the table.
clear : Empty the table by removing all its elements.

Dimostrazione : Sia M 0 ...., M n-1 sia la serie di operazioni eseguite su S, e sia M i0 , ...., M ik-1 sono le operazioni chiare all'interno della serie. Abbiamo quindi,

0<= i0 < .... < i k-1 <= n-1.

Let us also define i-1 = -1. The running time of operation Mij (a clear operation) is O(ij - ij-1), because at most ij - ij-1 -1 elements could have been added into the table (using the add operation) since the previous clear operation Mij-1 or since the beginning of the series.

Domanda:

  1. Perché e come -1 = -1 è definito?
  2. Non ho capito "perché al massimo io j - i j-1 -1 elementi potrebbero essere stati aggiunti alla tabella (usando l'operazione add) poiché operazione di cancellazione precedente M i j-1 o dall'inizio della serie ". Per favore spiegami di più su questa affermazione sul perché -1 è entrato nella foto.
posta zilcuanu 10.08.2014 - 07:22
fonte

1 risposta

2

Inizierò con la tua seconda domanda. Quella -1 deriva dal fatto che sia i j che i j-1 sono operazioni chiare, si desidera contare solo le operazioni di aggiunta intermedie, così da fare non è necessario contare i valori sinistro e destro. (Ad esempio ci sono 3 valori tra 3 e 7: 4, 5, 6).

La risposta alla tua prima domanda: perché è prima del primo elemento e funziona bene con il testo citato. (Ad esempio, supponiamo che il primo clear sia all'indice 2 ; tra i -1 = - 1 e i 0 = 2, ci sono 2 interi: 0 e 1, quindi la formula di i j -i j-1 -1 = 2 - (- 1) -1 = 2 funziona ancora bene). Potresti usare un anche il numero, ma sarebbe più confuso.

    
risposta data 10.08.2014 - 08:10
fonte

Leggi altre domande sui tag