[Java] Costo Computazionale
Ciao,
La traccia dell'esercizio è la seguente:
Si consideri una classe Sequenza che definisce gli array di interi di dimensione variabile.
• Scrivere le specifiche e il codice dell’operazione add(-)
• Stimare il costo ammortizzato dell’operazione
Tentativo di risoluzione:
Il metodo add() so già essere corretto. Esso aggiunge un intero $e$ nella prima posizione libera. Se non c'è spazio, si chiama il metodo enflate () dentro all'add() per aggiungere spazio.
Il mio problema consiste nel costo ammortizzato.
In classe avevamo affrontato la cosiddetta "strategia del raddoppio", ossia: (e qui vorrei sapere se il mio ragionamento è corretto) per ogni inserimento che “non ha spazio” si raddoppia la dimensione della tabella.
Sempre seguendo gli appunti ho:
$1. . . 10, 11 -> (1+20),....,20,21 -> (1 +40).....,40, 41->( 1+80)....n ->(10*2^{k}+1)$
$T(n) = n+ 10(1+2+2^{2}+...+2^{k}) = n+ 10*(2^{k+1}-1) = n +2*10*2^{k}-10 <=3n - 10 $
e pertanto $(T(n))/n <=3 \in O(1)$
La ultime due righe, ossia la stima l'ho capita dal punto di vista matematico, ma vorrei capire come si è arrivati a scrivere la cascata precedente? In particolare, il valori tra parentesi (1+20 per esempio), indicano il numero di posizioni create?
E' corretto dire che n è il numero di elementi aggiunti, giusto ?
La traccia dell'esercizio è la seguente:
Si consideri una classe Sequenza che definisce gli array di interi di dimensione variabile.
• Scrivere le specifiche e il codice dell’operazione add(-)
• Stimare il costo ammortizzato dell’operazione
Tentativo di risoluzione:
Il metodo add() so già essere corretto. Esso aggiunge un intero $e$ nella prima posizione libera. Se non c'è spazio, si chiama il metodo enflate () dentro all'add() per aggiungere spazio.
Il mio problema consiste nel costo ammortizzato.
In classe avevamo affrontato la cosiddetta "strategia del raddoppio", ossia: (e qui vorrei sapere se il mio ragionamento è corretto) per ogni inserimento che “non ha spazio” si raddoppia la dimensione della tabella.
Sempre seguendo gli appunti ho:
$1. . . 10, 11 -> (1+20),....,20,21 -> (1 +40).....,40, 41->( 1+80)....n ->(10*2^{k}+1)$
$T(n) = n+ 10(1+2+2^{2}+...+2^{k}) = n+ 10*(2^{k+1}-1) = n +2*10*2^{k}-10 <=3n - 10 $
e pertanto $(T(n))/n <=3 \in O(1)$
La ultime due righe, ossia la stima l'ho capita dal punto di vista matematico, ma vorrei capire come si è arrivati a scrivere la cascata precedente? In particolare, il valori tra parentesi (1+20 per esempio), indicano il numero di posizioni create?
E' corretto dire che n è il numero di elementi aggiunti, giusto ?
Risposte
Ma non c'è alcuna spiegazione a quella successione? Scritta così non mi è molto chiara. Normalmente si contano i valori scritti nell'array (anche se l'allocazione di memoria può avere un costo abbastanza elevato rispetto alla copia di valori). Suppongo che l'idea sia quella di partire da un array di 10 elementi. Fino a 10 elementi un solo valore viene scritto nell'array. Quando si inserisce l'11-esimo è tuttavia necessario allocare un nuovo array e copiare i vecchi valori. Si ha quindi che è necessario scrivere 11 elementi in questo caso (non mi è chiaro il perché del 20..). Ogni volta che inserisci l'elemento \((10 \cdot 2^k + 1)\)-esimo dovrai allocare un nuovo array e quindi copiare altrettanti valori nel nuovo array.
Esatto, scusami se non ho specificato !
L'array di partenza era formato da 10 elementi.
Probabilmente il 20 deriva dalla "strategia del raddoppio"... ovvero quando devo aggiungere l'11esimo elemento, alloca un nuovo array di dimensione doppia rispetto a quella precedente (come scritto a pag. 7 di http://twiki.di.uniroma1.it/pub/Intro_algo/AD/WebHome/RidimensionamentoTabeleDinamiche.pdf che ho trovato online)
è corretta questa mia interpretazione ?
L'array di partenza era formato da 10 elementi.
Probabilmente il 20 deriva dalla "strategia del raddoppio"... ovvero quando devo aggiungere l'11esimo elemento, alloca un nuovo array di dimensione doppia rispetto a quella precedente (come scritto a pag. 7 di http://twiki.di.uniroma1.it/pub/Intro_algo/AD/WebHome/RidimensionamentoTabeleDinamiche.pdf che ho trovato online)
è corretta questa mia interpretazione ?
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo