Algoritmi e Strutture Dati
Capitolo 2 - Analisi di algoritmi
Alberto Montresor
Università di Trento
This work is licensed under the Creative Commons Attribution-NonCommercial-ShareAlike License. To view
a copy of this license, visit http://creativecommons.org/licenses/by-nc-sa/2.5/ or send a letter to Creative
Commons, 543 Howard Street, 5th Floor, San Francisco, California, 94105, USA.
© Alberto Montresor
1
Valutare la complessità in tempo
Complessità in tempo: cosa serve?
✦Per stimare il tempo impiegato da un programma
✦
Per stimare il più grande input gestibile in tempi ragionevoli
✦
Per confrontare l'efficienza di algoritmi diversi
✦
Per ottimizzare le parti più importanti
✦
“Complessità”: “Dimensione” → “Tempo”
✦Dobbiamo definire “dimensione” e “tempo”!
✦
© Alberto Montresor
2
Dimensione dell'input
Criterio di costo logaritmico:
✦La taglia dell'input è il numero di bit necessari per rappresentarlo
✦
Esempio: moltiplicazione di numeri binari lunghi n bit
✦
Criterio di costo uniforme
✦La taglia dell'input è il numero di elementi che lo costituiscono
✦
Esempio: ricerca minimo in un array di n elementi
✦
In molti casi:
✦Possiamo assumere che gli “elementi” siano rappresentati da un numero
costante di bit
✦
Le due misure coincidono a meno di una costante moltiplicativa
✦
© Alberto Montresor
3
Definizione di tempo
Tempo = “Wall-clock” time:
✦Il tempo effettivamente impiegato per eseguire un algoritmo
✦
Dipende da troppi parametri:
✦bravura del programmatore
✦
linguaggio di programmazione utilizzato
✦
codice generato dal compilatore
✦
processore, memoria (cache, primaria, secondaria)
✦
sistema operativo, processi attualmente in esecuzione
✦
Dobbiamo considerare un modello astratto
✦
© Alberto Montresor
4
Definizione di tempo
Tempo = “# operazioni elementari”
✦Quali operazioni possono essere considerate elementari?
✦
Esempio: min(A, n)
✦
Modello di calcolo: rappresentazione astratta di un calcolatore
✦Astrazione:
deve semplificare dettagli, altrimenti è inutile
✦
Realismo:
deve riflettere la situazione reale
✦
“Potenza” matematica:
deve permettere di trarre conclusioni “formali” sul costo
✦
© Alberto Montresor
5
Da “Wikipedia”
© Alberto Montresor
6
Macchina di Turing
Testina
D a1 a2
…
Meccanismo di controllo
(Programma)
Nastro
Cella
Marcatore della prima
cella
La macchina:
legge il simbolo sotto la testina
modifica il proprio stato (finito) interno
scrive un nuovo simbolo nella cella
muove la testina a destra o a sinistra
Fondamentale nello studio della calcolabilità
✦
Non adatto per i nostri scopi
✦Livello troppo basso
✦
Non sufficientemente realistico
✦
© Alberto Montresor
7
Modello RAM
Random Access Machine (RAM)
✦Memoria:
✦Quantità infinita di celle di dimensione finita
✦
Accesso in tempo costante (indipendente dalla posizione)
✦
Processore (singolo)
✦
Set di istruzioni elementari simile a quelli reali:
✦
✦
somme, addizioni, moltiplicazioni, operazioni logiche, etc.
✦
istruzioni di controllo (salti, salti condizionati)
Costo delle istruzioni elementari
✦
Uniforme, ininfluente ai fini della valutazione (come vedremo)
✦
© Alberto Montresor
8
Tempo di calcolo di min()
Ogni istruzione richiede un tempo costante per essere eseguita
✦
Costante diversa da istruzione a istruzione
✦
Ogni istruzione viene eseguita un certo # di volte, dipendente da n
✦
© Alberto Montresor
9
Tempo di calcolo di binarySearch()
Il vettore viene suddiviso in due parti
✦
© Alberto Montresor
10
Tempo di calcolo di binarySearch()
Assunzioni
k
✦Per semplicità, assumiamo n potenza di 2: n =2
✦
L’elemento cercato non è presente (caso pessimo)
✦
Ad ogni suddivisione, scegliamo sempre la parte DX di dimensione n/2
(caso pessimo)
✦
Due casi
✦
Equazione di ricorrenza
✦
© Alberto Montresor
11
Tempo di calcolo di binarySearch()
Soluzione ricorrenza per sostituzione
k
✦Ricordate che n = 2 ⇒ k = log n
✦
© Alberto Montresor
12
Analisi di algoritmi
Analisi del caso pessimo
✦La più importante
✦
Il tempo di esecuzione nel caso peggiore è un limite superiore al tempo di
esecuzione per qualsiasi input
✦
Per alcuni algoritmi, il caso peggiore si verifica molto spesso
✦
Es.: ricerca di dati non presenti in un database
✦
Il caso medio è spesso cattivo quanto quello peggiore
✦
Vedi insertionSort()
✦
Analisi del caso medio
✦Difficile in alcuni casi: cosa si intende per “medio”?
✦
Distribuzione uniforme
✦
Analisi del caso ottimo
✦Può avere senso se l’input ha una distribuzione particolare
✦
© Alberto Montresor
13
Limiti asintotici superiori e inferiori
© Alberto Montresor
14
Torniamo alla matematica elementare...
Nei prossimi lucidi, vedremo alcuni
semplici algoritmi
✦Somme e moltiplicazioni (!)
2X2=5
✦
Ordinamento
✦
Vogliamo riflettere su:
✦In alcuni casi, si può migliorare quanto si ritiene “normale”
✦
In altri casi, è impossibile fare di meglio
✦
Qual è il rapporto fra un problema computazionale e l'algoritmo?
✦
© Alberto Montresor
15
Moltiplicare numeri complessi
Ricordate come moltiplicare due numeri complessi?
✦(a+bi)(c+di) = [ac – bd] + [ad + bc]i
✦
Input: a, b, c, d
✦
Output: ac-bd, ad+bc
Modello di calcolo:
✦Costo moltiplicazione: 1, costo addizione/sottrazione: 0.01
✦
Domande
✦Quanto costa l'algoritmo “banale” dettato dalla definizione?
✦
Potete fare di meglio? (Soluzione di Gauss)
✦
Qual è il ruolo del modello di calcolo?
✦
© Alberto Montresor
16
Moltiplicare numeri complessi
Questioni aperte...
✦Si può fare di meglio?
✦
Oppure, è possibile dimostrare che non si può fare di meglio?
✦
Alcune riflessioni
✦In questo modello “estremamente semplice”, effettuare 3 moltiplicazioni
invece di 4 risparmia il 25% del costo
✦
Esistono contesti in cui effettuare 3 moltiplicazioni invece di 4 può
produrre un risparmio maggiore
✦
© Alberto Montresor
17
Sommare numeri binari
Algoritmo elementare della somma - sum()
✦richiede di esaminare tutti gli n bit
✦costo totale cn (c ≡ costo per sommare tre bit e generare riporto)
✦
Domanda
✦Esiste un metodo più efficiente?
✦
11101111111111
1 0 1 1 0 0 1 1 0 1 1 0 1 1 1+
111101101101011
1101010100100010
© Alberto Montresor
18
Moltiplicare numeri binari
Algoritmo “elementare” del prodotto - prod()
✦
n2
© Alberto Montresor
*******
*******
*******
*******
*******
*******
*******
*******
*******
x
19
Moltiplicare numeri binari
Confronto fra i costi di esecuzione
✦Somma: Tsum(n) = c1n
✦
Prodotto: Tprod(n) = c2n2 + c3n
✦
Si potrebbe erroneamente concludere che...
✦Il problema della moltiplicazione è inerentemente più costoso del
problema dell'addizione
✦
“Conferma” la nostra esperienza
✦
© Alberto Montresor
20
Moltiplicare numeri binari
Confronto fra problemi
✦Per provare che il problema del prodotto è più costoso del problema della
somma, dobbiamo provare che non esiste una soluzione in tempo lineare
per il prodotto
✦
Abbiamo confrontato gli algoritmi, non i problemi
✦A parità di dimensione dell'input:
l'algoritmo di somma studiato alle elementari è più efficiente dell'algoritmo
del prodotto studiato alle elementari
✦
Nel 1960, Kolmogorov enunciò in una conferenza che l’algoritmo per la
moltiplicazione era ottimo, ovvero non si può fare meglio di così
✦
Una settimana dopo, fu provato il contrario!
✦
© Alberto Montresor
21
Moltiplicare numeri binari
Un metodo algoritmico: divide-et-impera
✦Divide: dividi il problema in sottoproblemi di dimensioni inferiori
✦
Impera: risolvi i sottoproblemi in maniera ricorsiva
✦
Combina: unisci le soluzioni dei sottoproblemi in modo da ottenere la
risposta del problema principale
✦
Moltiplicazione ricorsiva
n/2 + b
✦X = a 2
✦
Y = c 2n/2 + d X
✦
XY = ac 2n + (ad+bc) 2n/2 + bd
X
a
b
Y
c
d
✦
Nota:
✦
Moltiplicare per 2t ≡ shift di t posizioni, in tempo lineare
✦
Sommare due vettori di bit anch’esso in tempo lineare
✦
© Alberto Montresor
22
Moltiplicare numeri binari
Algoritmo pdi(): prodotto divide-et-impera
✦
Costo della procedura pdi()
✦
© Alberto Montresor
23
Svolgere la ricorsione
0
nn
1
2
n/2
n/2
n/4
n/4
i
+
n/4
n/4
n/2
n/4
n/2 +
n/4
n/4
+ n/2
n/2
n/4
n/4
n/4
n/2
n/2
n/4
n/4
n/4
n/4
n/4
n/4
i
Livello i: 4i istanze
n/2
Leveldii dimensione
is the sum of
4i copies of n/2i
..........................
log2 n
1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+
1+1+1+1+1+1+1+1
............................................................................
.......................
© Alberto Montresor
24
Moltiplicare numeri binari
Confronto fra algoritmi: tutto questo lavoro per niente?
2
✦Tprod(n) = O(n )
✦
Tpdi(n) = O(n2)
✦
La versione ricorsiva chiama se stessa 4 volte.
n/2 + b
✦X = a 2
✦
Y = c 2n/2 + d
✦
XY = ac 2n + (ad+bc) 2n/2 + bd
✦
Domanda
✦E' possibile ridurre il numero di moltiplicazioni?
✦
© Alberto Montresor
25
Moltiplicazione di Karatsuba (1962)
Gaussified-product (Karatsuba 1962)
✦A1 = ac
✦
A3 = bd
✦
m = (a+b)(c+d)=ac+ad+bc+bd
✦
A2 = m−A1−A3=ad+bc
✦
© Alberto Montresor
26
Moltiplicare numeri binari
Gaussified-product (Karatsuba 1962)
✦
Esempio:
✦
Tpdi(106) =1012
✦
Tkaratsuba(106) = 3⋅109
✦
Conclusioni
✦L'algoritmo “naif” non è sempre il migliore...
✦
... può esistere spazio di miglioramento...
✦
... a meno che non sia possibile dimostrare il contrario!
✦
© Alberto Montresor
27
E non finisce qui...
1963: Toom-Cook
log 5/log 3) ~ O(n1.465)
✦Noto come algoritmo Toom3, ha complessità O(n
✦
Karatsuba = Toom2
✦
Moltiplicazione normale = Toom1
✦
1971: Schönhage–Strassen
✦Complessità O(n log n (log log n))
✦
Basato su Fast Fourier Transforms
✦
2007: Martin Fürer
O(log* n))
✦Complessità O(n log n 2
✦
Limite inferiore:
✦Ω(n log n) (congettura)
✦
© Alberto Montresor
28
GNU Multiple Precision Arithmetic Library
Utilizzata da Mathematica, Maple, etc.Utilizza Schönhage–Strassen quando
l’input è più lungo di k parole di 64 bit, con k compreso fra 1728 e 11520 a
seconda dell’architettura
✦
© Alberto Montresor
29
Ordinamento
Problema dell'ordinamento
✦Input: una sequenza A di n numeri <a1, a2, ..., an>
✦
Output: una permutazione B=<b1, b2, ..., bn> di A tale per cui
b1 ≤ b2 ≤ ... ≤ bn
✦
Algoritmo “naif”
✦Generare tutte le permutazioni (n!) e verificare in tempo O(n)
se sono ordinate
✦
Costo totale: O(n n!)
✦
© Alberto Montresor
30
Selection sort
Complessità (caso medio, pessimo, ottimo)
✦
© Alberto Montresor
31
Insertion Sort
Algoritmo efficiente per ordinare piccoli insiemi di elementi
✦
Come ordinare una sequenza di carte da gioco “a mano”
✦
© Alberto Montresor
32
Insertion Sort - Analisi
Per questo algoritmo:
✦Il costo di esecuzione non dipende solo dalla dimensione...
✦
ma anche dalla distribuzione dei dati in ingresso
✦
Domande
✦Qual è il costo nel caso il vettore sia già ordinato?
✦
Qual è il costo nel caso il vettore sia ordinato in ordine inverso?
✦
Cosa succede “in media”?
✦
Informalmente
✦
© Alberto Montresor
33
Merge Sort
Insertion Sort
✦E' basato su un approccio incrementale
(A[1...j-1] ordinato, aggiungi A[j])
✦
Merge Sort
✦E' basato sulla tecnica divide-et-impera vista in precedenza
✦
Divide:
✦
Dividi l'array di n elementi in due sottovettori di n/2 elementi
✦
Impera:
✦
Chiama MergeSort ricorsivamente su i due sottovettori
✦
Combina:
✦
Unisci (merge) le due sequenze ordinate
✦
© Alberto Montresor
34
Merge Sort
Il nucleo di Merge Sort è nel passo combina (merge)
✦merge(A, primo, ultimo, mezzo)
✦A è un array di lunghezza n
✦
primo, ultimo, mezzo indici tali per cui
✦
1 ≤ primo ≤ mezzo < ultimo ≤ n
La procedura merge() suppone che i sottovettori A[primo...mezzo] e
A[mezzo+1...ultimo] siano ordinati
✦
I due vettori vengono fusi in un unico sottovettore ordinato
A[primo...ultimo]
✦
Qual è l'idea?
✦Fondere i due sottovettori “sfruttando” il fatto che sono ordinati
✦
© Alberto Montresor
35
Merge Sort
© Alberto Montresor
36
Merge Sort
Come funziona merge():
A
B
✦
1 5 7 + 2 4 6
5 7 + 2 4 6
1
5 7 +
4 6
1 2
5 7 +
6
1 2 4
7 +
6
1 2 4 5
7 +
+
1 2 4 5 6
7
1 2 4 5 6
1 2 4 + 5 6 7
Domanda
✦ Costo computazionale di merge()
✦
© Alberto Montresor
37
Merge Sort
Programma completo
✦Chiama ricorsivamente se stesso e usa merge() per unire i risultati
✦
Caso base: sequenze di lunghezza ≤ 1 sono già ordinate
✦
© Alberto Montresor
38
Merge Sort
Partizionamento
Merge
© Alberto Montresor
39
Analisi di Merge-Sort
Una assunzione semplificativa
k
✦n=2 , ovvero l'altezza dell'albero di sottodivisioni è esattamente k
✦
tutti i sottovettori hanno dimensioni che sono potenze esatte di 2
✦
Costi di Merge Sort
✦
Risoluzione della ricorrenza
✦
Domanda
✦Ricavare questo risultato svolgendo l’equazione di ricorrenza
✦
© Alberto Montresor
40
Confronto fra ordini di grandezza
© Alberto Montresor
41
Limitazioni inferiori e algoritmi ottimi
Dato un problema
✦Se trovate un algoritmo A con complessità O(g(n)), avete stabilito un
limite superiore alla complessità del problema - g(n)
✦
Se dimostrate che qualunque algoritmo per il problema deve avere
complessità Ω(f(n)), avete stabilito un limite inferiore alla complessità
del problema - f(n)
✦
Se f(n)=g(n), allora A è un algoritmo ottimo
✦
© Alberto Montresor
42
Limitazioni inferiori - tecniche
Dimensione dei dati
✦Se un problema ha in ingresso n dati e richiede di esaminarli tutti, allora
una limitazione inferiore della complessità è Ω(n)
✦
Esempio: sommare due numeri binari
✦
Eventi contabili
✦Se un problema richiede che un certo evento sia ripetuto almeno n volte,
allora una limitazione inferiore della complessità è Ω(n)
✦
Esempio: ricerca del minimo richiede almeno n-1 confronti
✦
Oracolo
✦Se un oracolo, utilizzando una certa regola ignota all’algoritmo, “divina”
ad ogni opportunità la situazione più sfavorevole, allora combattendo
contro di esso si può individuare una limitazione inferiore
✦
Esempio: merge()
✦
© Alberto Montresor
43
Limitazioni inferiori
Caveat emptor!
✦Le tecniche illustrate sono semplici, ma nascondono sottigliezze
✦
Fare attenzioni alle assunzioni di base
✦
Ricerca in vettore ordinato: O(log n), non O(n)!
✦
Ricerca del minimo in vettore ordinato: O(1), non O(n)!
✦
Esempio più complesso: ordinamento
✦Limitazione inferiore Ω(n) - perché?
✦
Limitazione superiore O(n log n)
✦
Possiamo “restringere” questo scarto?
✦
Più avanti mostremo...
✦
© Alberto Montresor
44
Limitazioni inferiori
Caveat emptor!
✦Le tecniche illustrate sono semplici, ma nascondono sottigliezze
✦
Fare attenzioni alle assunzioni di base
✦
Ricerca in vettore ordinato: O(log n), non O(n)!
✦
Ricerca del minimo in vettore ordinato: O(1), non O(n)!
✦
Esempio più complesso: ordinamento
✦Limitazione inferiore Ω(n) - perché?
✦
Limitazione superiore O(n log n)
✦
Possiamo “restringere” questo scarto?
✦
Più avanti mostreremo...
✦
che Merge Sort è ottimo, in quanto è possibile dimostrare che
Ω(n log n) è un limite inferiore all’ordinamento per gli algoritmi
basati su confronti
✦
© Alberto Montresor
45
Counting Sort
Come funziona:
✦I numeri da ordinare sono compresi in un range [1..k]
✦
Costruire un array B[1..k] che conta il numero di volte che compare un
valore in [1..k]
✦
Ricollocare i valori così ottenuti in A
✦
© Alberto Montresor
46
Counting Sort
Complessità
✦O(n+k)
✦
Se k è O(n), allora la complessità è O(n)
✦
Discussione su limite inferiore
✦Counting Sort non è basato su confronti
✦
Abbiamo cambiato le condizioni di base
✦
Se k è O(n3), questo algoritmo è peggiore di tutti quelli visti finora
✦
© Alberto Montresor
47
Tecniche di analisi
Per risolvere le relazioni di ricorrenza
✦Analisi per sostituzione (accennata)
✦
Analisi per livelli (accennata)
✦
Relazioni di ricorrenza comuni
✦
Ricorrenze lineari di ordine costante
✦
Ricorrenze lineari con partizione bilanciata
✦
Analisi per tentativi
✦
Alla lavagna!
✦
© Alberto Montresor
48
Analisi ammortizzata
Si considera il tempo richiesto per eseguire, nel caso pessimo, un'intera
sequenza di operazioni
Sequenza
✦Operazioni costose e meno costose
✦
Se operazioni più costose sono poco frequenti, allora il loro costo può
essere ammortizzato dalle operazioni meno costose
✦
Importante differenza
✦Analisi del caso medio:
✦basata su probabilità, su singola operazione
✦
Analisi ammortizzata:
✦
deterministica, su operazioni multiple, caso pessimo
✦
© Alberto Montresor
49
Metodi per l'analisi ammortizzata
Metodo dell'aggregazione
✦Si calcola la complessità O(f(n)) per eseguire n operazioni in sequenza nel
caso pessimo
✦
Il costo ammortizzato di una singola operazione è O(f(n)/n)
✦
Metodo degli accantonamenti (o del contabile)
✦Alle operazioni vengono assegnati costi ammortizzati che
possono essere maggiori/minori del loro costo effettivo
✦
Provare che la somma dei costi ammortizzati è un
limite superiore al costo effettivo
✦
Metodo del potenziale
✦Lo stato del sistema viene descritto tramite differenze di potenziale
✦
Tecnica derivata dalla fisica
✦
© Alberto Montresor
50
Esempio
Contatore binario
✦Implementiamo un contatore binario di k bit con un array di bit
✦
Un numero binario x registrato in A ha il bit meno significativo in A[0] e il
più significativo in A[k-1] per cui:
✦
Supponiamo che A venga usato per contare a partire da x=0 usando
l’operazione di incremento
✦
© Alberto Montresor
51
Esempio - Contatore
x
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
A[7] A[6] A[5] A[4] A[3] A[2] A[1] A[0]
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
© Alberto Montresor
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
0
0
0
0
0
1
1
1
1
0
0
0
0
1
1
1
1
0
0
0
1
1
0
0
1
1
0
0
1
1
0
0
1
1
0
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
costo
0
1
3
4
7
8
10
11
15
16
18
19
22
23
25
26
31
52
Esempio - Contatore
Analisi “grossolana”
✦Una singola operazione di incremento richiede tempo O(k) nel caso
pessimo
✦
Limite superiore O(nk) per una sequenza di n incrementi
✦
Considerazioni per un'analisi più stretta
✦Possiamo però osservare che il tempo necessario ad eseguire l’intera
sequenza è proporzionale al numero di bit che vengono modificati
✦
Quanti bit vengono modificati?
✦
© Alberto Montresor
53
Esempio: funzionamento
x
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
A[7] A[6] A[5] A[4] A[3] A[2] A[1] A[0]
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
© Alberto Montresor
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
0
0
0
0
0
1
1
1
1
0
0
0
0
1
1
1
1
0
0
0
1
1
0
0
1
1
0
0
1
1
0
0
1
1
0
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
costo
0
1
3
4
7
8
10
11
15
16
18
19
22
23
25
26
31
54
Esempio – Metodo dell'aggregazione
Dalla simulazione si vede che:
✦A[0] viene modificato ad ogni incremento del contatore,
✦
A[1] viene modificato ogni 2 incrementi,
✦
A[2] viene modificato ogni 4 incrementi....
✦
In generale,
i
✦A[i] viene modificato ogni 2 incrementi
✦
Quindi:
✦Costo aggregato:
✦
Costo ammortizzato: 2n/n = 2 = O(1)
✦
© Alberto Montresor
55
Metodo degli accantonamenti o del contabile
Si assegna un costo ammortizzato distinto(*) ad ognuna delle operazioni
possibili
✦
Il costo ammortizzato può essere diverso dal costo effettivo
✦Le operazioni meno costose vengono caricate di un costo aggiuntivo detto
credito
✦costo ammortizzato = costo effettivo + credito prodotto
✦
I crediti accumulati saranno usati per pagare le operazioni più costose
✦
costo ammortizzato = costo effettivo – credito consumato
✦
(*) Nell'aggregazione, abbiamo calcolato costo ammortizzato costante
© Alberto Montresor
56
Come assegnare costi ammortizzati?
Lo scopo è:
✦dimostrare che la somma dei costi ammortizzati ai è un limite superiore ai
costi effettivi ci:
✦
dimostrare che il valore così ottenuto è “poco costoso”
✦
Alcuni punti da ricordare
✦La dimostrazione deve essere valida per tutte le sequenze di input
(caso pessimo)
✦
Il credito è espresso dalla seguente formula e quindi è positivo
✦
© Alberto Montresor
57
Esempio – Metodo degli accantonamenti
Costi
✦Costo effettivo dell'operazione increment(): d
(dove d è il numero di bit che cambiano valore)
✦
Costo ammortizzato dell'operazione increment(): 2
✦
1 per cambio del bit da 0 a 1 (costo effettivo)
✦
1 per il futuro cambio dello stesso bit da 1 a 0
✦
Ne segue che:
✦
in ogni istante, il credito è pari al numero di bit 1
attualmente presenti
✦
Costo totale ammortizzato: O(n)
✦
© Alberto Montresor
58
Metodo del potenziale
Come funziona
✦Si associa alla struttura dati D una funzione di potenziale Φ(D)
✦
Requisiti:
✦
le operazioni meno costose devono incrementare Φ(D)
✦
le operazioni più costose devono decrementare Φ(D)
✦
Costo ammortizzato:
✦sommatoria del costo effettivo e della variazione di potenziale
✦
© Alberto Montresor
59
Metodo del potenziale
Il costo ammortizzato di una sequenza di n operazioni è:
✦
Se la variazione di potenziale Φ(Dn)-Φ(D0) è non negativa:
✦il costo ammortizzato A è un limite superiore al costo reale
✦
Altrimenti:
✦la variazione di potenziale negativa deve essere compensata da un
aumento adeguato del costo ammortizzato delle operazioni.
✦
© Alberto Montresor
60
Esempio 2 – Metodo del potenziale
Scegliamo come funzione potenziale Φ(A) il numero bit 1 presenti nel
contatore
✦
operazione
add
costo
effettivo
1+t
differenza di
potenziale
-t+1
costo
ammortizzato
2
Nota:
✦t è il numero di bit 1 incontrati a partire dal meno significativo, prima di
incontrare un bit 0
✦
Partendo dal valore 0
✦All'inizio, zero bit accesi → Φ(A0) = 0
✦
Alla fine, Φ(An) ≥ 0 → la differenza di potenziale è non negativa
✦
© Alberto Montresor
61
Esercizi
Esercizio 1
✦Dato un array A[1..n] di interi e un intero v, descrivere un algoritmo che
determini se esistono due elementi in A la cui somma è esattamente v
✦
Esercizio 2
✦Dato un array A[1..n] di interi positivi, descrivere un algoritmo O(n) che
determini se esistono due elementi in A la cui somma è esattamente 17
✦
Esercizio 3
✦Siano date n monete d'oro, tutte dello stesso peso tranne una contraffatta
che pesa meno, ed una bilancia con due piatti.Disegnare un algoritmo per
individuare la moneta contraffatta in al più log n pesate.
✦
© Alberto Montresor
62