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.
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”!
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
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
✦
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
✦
5
Da “Wikipedia”
6
Macchina di Turing
Testina
D a1 a2 …
Nastro
Cella
Marcatore della prima
cella
Meccanismo di controllo
(Programma)
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
7
Modello RAM
Random Access Machine (RAM)
✦
✦
Memoria:
✦Quantità infinita di celle di dimensione finita
✦
✦
Processore (singolo)
✦
✦
Accesso in tempo costante (indipendente dalla posizione)
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)
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
9
Tempo di calcolo di binarySearch()
Il vettore viene suddiviso in due parti
✦
10
Tempo di calcolo di binarySearch()
Assunzioni
✦
✦
Per semplicità, n =2k è una potenza di 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
11
Tempo di calcolo di binarySearch()
Soluzione ricorrenza per sostituzione
✦
✦
Ricordate che n = 2k ⇒ k = log n
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
✦
13
Limiti asintotici superiori e inferiori
14
Algoritmi: primi esempi
Nei prossimi lucidi, vedremo alcuni
semplici algoritmi
✦
✦
Somme e moltiplicazioni (!)
✦
Ordinamento
2X2=5
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?
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?
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
✦
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?
✦
**************
* * * * * * * * * * * * * * *+
***************
****************
18
Moltiplicare numeri binari
Algoritmo “elementare” del prodotto - prod()
✦
n2
*******
*******
*******
*******
*******
*******
*******
*******
*******
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
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 è più efficiente dell'algoritmo del prodotto
✦
Questione aperta se esista un algoritmo in tempo lineare
per il prodotto
✦
✦
Esiste comunque la possibilità di migliorare
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
a
b
n/2
✦Y = c 2
+d
c
d
n
n/2 + bd
✦XY = ac 2 + (ad+bc) 2
✦Nota:
t
✦Moltiplicare per 2 ≡ shift di t posizioni, in tempo lineare
✦Sommare due vettori di bit anch’esso in tempo lineare
✦
22
Moltiplicare numeri binari
Algoritmo pdi(): prodotto divide-et-impera
✦
Costo della procedura pdi()
✦
23
Svolgere la ricorsione
24
Moltiplicare numeri binari
Confronto fra algoritmi: tutto questo lavoro per niente?
✦
✦
Tprod(n) = O(n2)
✦
Tpdi(n) = O(n2)
La versione ricorsiva chiama se stessa 4 volte.
✦
✦
X = a 2n/2 + b
✦
Y = c 2n/2 + d
✦
XY = ac 2n + (ad+bc) 2n/2 + bd
Domanda
✦
✦
E' possibile ridurre il numero di moltiplicazioni?
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
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!
✦
27
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!)
28
Selection sort
Complessità (caso medio, pessimo, ottimo)
✦
29
Insertion Sort
Algoritmo efficiente per ordinare piccoli insieme di elementi
✦
Come ordinare una sequenza di carte da gioco “a mano”
✦
30
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 l'array sia già ordinato?
✦
Qual è il costo nel caso l'array sia ordinato in ordine inverso?
✦
Cosa succede “in media”?
✦
Informalmente
31
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:
✦
✦
Impera:
✦
✦
Dividi l'array di n elementi in due sottovettori di n/2 elementi
Chiama MergeSort ricorsivamente su i due sottovettori
Combina:
✦
Unisci (merge) le due sequenze ordinate
32
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
33
Merge Sort
34
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()
35
Merge Sort
Programma completo
✦
✦
Chiama ricorsivamente se stesso e usa merge() per unire i risultati
✦
Caso base: sequenze di lunghezza ≤ 1 sono già ordinate
36
Merge Sort
37
Analisi di Merge-Sort
Una assunzione semplificativa
✦
✦
n=2k, 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
38
Confronto fra ordini di grandezza
39
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 all complessità
del problema - f(n)
✦
✦
Se f(n)=g(n), allora A è un algoritmo ottimo
40
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()
✦
41
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...
42
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
✦
43
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
44
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
45
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!
✦
46
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
47
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
48
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
✦
49
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
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
50
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?
51
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
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 – 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)
53
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
54
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
55
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)
✦
56
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
57
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.
✦
58
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
Caso 1: Partendo dal valore 0
✦
✦
All'inizio, zero bit accesi → Φ(A0) = 0
✦
Alla fine, Φ(An) ≥ 0 → la differenza di potenziale è non negativa
59
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.
✦
60