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:
- Perché e come -1 = -1 è definito?
- 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.