Riassunto Storie permesse storie proibite, di Valeria Ugazio
Complessità del problema Se non facciamo ipotesi sul tipo degli elementi della sequenza le uniche...
-
Upload
samuela-simona -
Category
Documents
-
view
214 -
download
0
Transcript of Complessità del problema Se non facciamo ipotesi sul tipo degli elementi della sequenza le uniche...
![Page 1: Complessità del problema Se non facciamo ipotesi sul tipo degli elementi della sequenza le uniche operazioni permesse sono confronti e assegnazioni. Problema.](https://reader036.fdocumenti.com/reader036/viewer/2022082920/5542eb74497959361e8dcb3c/html5/thumbnails/1.jpg)
Complessità del problema
Se non facciamo ipotesi sul tipo degli elementi della sequenza le uniche operazioni permesse sono confronti e assegnazioni.
Problema dell’ordinamento
Input: sequenza a1,a2,...,an di elementi su cui è definito un ordine
Output: a'1,a'2,...,a'n permutazione di a1,a2,...,an tale che a'1 ≤ a'2 ≤ ... ≤ a'n
![Page 2: Complessità del problema Se non facciamo ipotesi sul tipo degli elementi della sequenza le uniche operazioni permesse sono confronti e assegnazioni. Problema.](https://reader036.fdocumenti.com/reader036/viewer/2022082920/5542eb74497959361e8dcb3c/html5/thumbnails/2.jpg)
Siccome siamo interessati ad un limite inferiore possiamo contare solo alcune delle operazioni.Se un certo limite inferiore vale per il tempo richiesto per eseguire tali operazioni a maggior ragione varrà per il tempo calcolo totale.
Noi conteremo solo i confronti e dimostreremo che nel caso pessimo il numero di confronti è Ω(n log n).
Per fare questo è utile rappresentare la struttura di un algoritmo mediante un albero delle decisioni.
![Page 3: Complessità del problema Se non facciamo ipotesi sul tipo degli elementi della sequenza le uniche operazioni permesse sono confronti e assegnazioni. Problema.](https://reader036.fdocumenti.com/reader036/viewer/2022082920/5542eb74497959361e8dcb3c/html5/thumbnails/3.jpg)
1:2
2:3
1:32:3
1:3>≤≤ >
Esempio. Albero delle decisioni di Insertion-Sort con un array di 3 elementi.
≤ >
≤ >≤ >
Insertion-Sort(A) n = A.length for j = 2 to n i = j – 1 while i ≥ 1 and A[i]>A[i+1] scambia A[i] con A[i+1] i = i – 1
![Page 4: Complessità del problema Se non facciamo ipotesi sul tipo degli elementi della sequenza le uniche operazioni permesse sono confronti e assegnazioni. Problema.](https://reader036.fdocumenti.com/reader036/viewer/2022082920/5542eb74497959361e8dcb3c/html5/thumbnails/4.jpg)
Se l’algoritmo è corretto le foglie devono essere etichettate con ogni permutazione possibile dell’input. Perché?
1:2
a,b,c
a,b,c(1,2,3)
a,c,b(1,2,3)
c,b,a(1,2,3)
>≤b,c,a
(1,2,3)
b,a,c(1,2,3)≤ >
c,a,b(1,2,3)
Esempio. Albero delle decisioni di Insertion-Sort con un array di 3 elementi.
2:3a,b,c ≤ >
1:3b,a,c
≤ >2:3
b,c,a≤ >
1:3a,c,b
![Page 5: Complessità del problema Se non facciamo ipotesi sul tipo degli elementi della sequenza le uniche operazioni permesse sono confronti e assegnazioni. Problema.](https://reader036.fdocumenti.com/reader036/viewer/2022082920/5542eb74497959361e8dcb3c/html5/thumbnails/5.jpg)
Le permutazioni di 1,2,...,n sono n! e quindi l’albero delle decisioni deve avere almeno n! foglie.
Dunque nel caso pessimo l’algoritmo deve eseguire almeno log2(n!) confronti.
Ma un albero binario con N foglie deve avere altezza almeno pari a log2(N).
Esercizio: Dimostrarlo per induzione su N.
![Page 6: Complessità del problema Se non facciamo ipotesi sul tipo degli elementi della sequenza le uniche operazioni permesse sono confronti e assegnazioni. Problema.](https://reader036.fdocumenti.com/reader036/viewer/2022082920/5542eb74497959361e8dcb3c/html5/thumbnails/6.jpg)
e quindi per ogni algoritmo generale di ordinamento.
Ma
Possiamo concludere che Ω(n log n) è un limite inferiore per la complessità del problema dell’ordinamento.
)log()(max nnnT Alg
)log(2
log2
1
2log
2
2log)!(log
22
2
22
nn
nnn
nn
nn
n
![Page 7: Complessità del problema Se non facciamo ipotesi sul tipo degli elementi della sequenza le uniche operazioni permesse sono confronti e assegnazioni. Problema.](https://reader036.fdocumenti.com/reader036/viewer/2022082920/5542eb74497959361e8dcb3c/html5/thumbnails/7.jpg)
L’algoritmo di ordinamento Heapsort risolve il problema dell’ordinamento con complessità massima
)log()(max nnOnT HS
Dunque O(n log n) è limite superiore per la complessità del problema dell’ordinamento.
Siccome limite superiore e inferiore coincidono (n log n) è limite stretto per il problema dell’ordinamento.
![Page 8: Complessità del problema Se non facciamo ipotesi sul tipo degli elementi della sequenza le uniche operazioni permesse sono confronti e assegnazioni. Problema.](https://reader036.fdocumenti.com/reader036/viewer/2022082920/5542eb74497959361e8dcb3c/html5/thumbnails/8.jpg)
Considerazione sul limite inferiore Ω(n log n) per l’ordinamento
ATTENZIONE:
Il limite inferiore Ω(n log n) da noi dimostrato vale solo per algoritmi di ordinamento generali, ossia algoritmi che non fanno alcuna ipotesi sul tipo degli elementi da ordinare: le uniche operazioni ammesse su tali elementi sono confronti e assegnazioni.
![Page 9: Complessità del problema Se non facciamo ipotesi sul tipo degli elementi della sequenza le uniche operazioni permesse sono confronti e assegnazioni. Problema.](https://reader036.fdocumenti.com/reader036/viewer/2022082920/5542eb74497959361e8dcb3c/html5/thumbnails/9.jpg)
Il limite inferiore Ω(n log n) vale anche per ordinare numeri reali sui quali, oltre a confronti ed assegnazioni, si possono usare anche le quattro operazioni aritmetiche.
In questo caso la dimostrazione del limite inferiore è molto più difficile e si basa su alcuni risultati di geometria algebrica.
La dimostrazione si può trovare nel testo di Geometria Computazionale di F. Preparata.