Relazioni di ricorrenza e algoritmi di ordinamento PDF

Relazioni di ricorrenza e algoritmi di ordinamento di complessità n log n March 26, 2020 Obiettivi: studiare la complessità degli algoritmi ricorsivi e analizzare gli algoritmi di ordi...

Relazioni di ricorrenza e algoritmi di ordinamento di complessità n log n March 26, 2020 Obiettivi: studiare la complessità degli algoritmi ricorsivi e analizzare gli algoritmi di ordinamento di complessità n log n. Argomenti: relazioni di ricorrenza (a partizione costante e a partizione bilanciata) e relative teoremi, metodo iterativo, merge-sort, quick-sort. Il numero di operazioni eseguite (il tempo di esecuzione) di un algoritmo ricorsivo è spesso semplice da esprimere con una relazione di ricorrenza. Si possono distinguere due casi: la chiamata ricorsiva diminuisce la dimensione del input (oppure l'input stesso) di un costante: in questo caso si ottiene una relazione di ricorrenza a partizione costante; la chiamata ricorsiva diminuisce la dimensione del input (oppure l'input stesso) di un certo fattore (per esempio, dimezza l'input): in questo caso si ottiene una relazione di ricorrenza a partizione bilanciata. 1 Relazione di ricorrenza a partizione costante Analizziamo l'algoritmo ricorsivo che calcola il fattoriale: 1: Fattoriale(n) 2: if n < 2 then return 1 3: return n·Fattoriale(n − 1) Considerando ogni riga come singola operazione, si può contare il numero di operazioni T (n) col seguente ragionamento: se n < 2 allora viene eseguita solo la riga 2; se n ≥ 2 allora viene eseguita la riga 2 e la chiamata Fattoriale(n−1) della riga 3 dà luogo a T (n−1) operazioni in più. Se ne ottiene la seguente relazione di ricorrenza:  1 n1: cn − 1 = cn b + d c−1 Di conseguenza la soluzione è cn − 1 T (n) = cn b + d c−1 Verichiamo la soluzione col principio di induzione. Caso base. Con n = 0 la soluzione funziona: c0 b + cc−1 0 −1 d = b = T (0). Passo induttivo. Dobbiamo dimostrare che T (n) = cn b + cc−1 n −1 d (l'ipotesi induttiva) implica T (n + 1) = n+1 cn+1 −1 c b+ c−1 d: secondo la relazione di ricorrenza: T (n + 1) = cT (n) + d utilizzando l'ipotesi induttiva: cn − 1   = c cn b + d +d c−1 n+1 c −c = cn+1 b + d+d c−1 cn+1 − c + c − 1 = cn+1 b + d c−1 cn+1 − 1 = cn+1 b + d c−1 Quindi la soluzione è corretta. T (n) La funzione T (n) ∈ Θ(cn ) (per vericarlo è suciente considerare limn→∞ cn ). 1.1 Quick-sort Quick-sort. L'idea dell'algoritmo: si seleziona un elemento del vettore, detto perno, attorno al quale si riorganizzano gli altri elementi in modo tale che gli elementi più piccoli o uguali al perno si trovino in posizioni precedenti a quella del perno e gli elementi più grandi in posizioni successive; poi si ripete lo stesso procedimento a sinistra e a destra del perno. 3  Quick-Sort(A[1..n]) if n > 1 then p ← Partition(A[1..n]). partizionamento porta il perno nella posizione p if p > 2 then. se prima del perno ci sono almeno 2 elementi Quick-Sort(A[1..p − 1]) end if if p A then j ←j−1 else scambia A[i] con A[j] i ← i + 1, j ← j − 1 end if end if end while scambia A con A[j] return j Il partizionamento eettuato da Partition utilizza A come perno e considera una volta tutti gli elementi del sottovettore che deve riorganizzare. Di conseguenza il numero di operazioni eettuate da Partition può essere considerato come TP (n) = an con una costante a. Il caso peggiore è quello nel quale il perno capita essere sempre o il minimo o il massimo del sottovettore riorganizzato da Partition. In questo caso una sola chiamata ricorsiva viene eettuata. Nel caso peggiore la relazione di ricorrenza per Quick-Sort ha la seguente forma:   c n=1 c n=1 T (n) = = T (n − 1) + TP (n) + b n>1 T (n − 1) + an + b n > 1 con tre costanti a, b e c. 4 Analizziamo la relazione di ricorrenza col metodo dell'iterazione: T (n) = T (n − 1) + an + b = T (n − 2) + a(n − 1) + b + an + b = = T (n − 3) + a(n − 2) + b + a(n − 1) + b + an + b = dopo k≤n iterazioni: k−1 X = T (n − k) + a (n − i) + kb i=0 dopo n−1 iterazioni: n−2 X = T (1) + a (n − i) + (n − 1)b i=0 n−2 X n X =c+a (n − i) + (n − 1)b = c + a i + (n − 1)b i=0 i=2 da dove si evince che T (n) ∈ Θ(n2 ) e quindi Quick-Sort è quadratico nel caso peggiore. Il seguente teorema fornisce una ricetta per trovare un limite superiore in senso O data una relazione di ricorrenza di ordine costante. Teorema: Siano a1 ,..., ah costanti intere non negative, c, d e β costanti reali positive tale che  d se n≤m≤h T (n) = Ph β i=1 ai T (n − i) + cn se n>m Ph Posto a= i=1 ai T (n) ∈ O(nβ+1 ) se a=1 β n T (n) ∈ O(n a ) se a≥2 (Il teorema precedente opera con O perché in certi casi la relazione di ricorrenza permette un conne superiore più stretto di quello indicato dal teorema.) Il teorema si può applicare ai esempi discussi precedentemente (fattoriale, Hanoi, caso peggiore di Quick- Sort). 2 Relazione di ricorrenza a partizioni bilanciate Un approccio generale per la soluzione di problemi computazionali è il il divide et impera. L'approccio consiste nel dividere ricorsivamente un problema in due o più sotto-problemi sino a che i sotto-problemi diventino di semplice risoluzione, quindi, si combinano le soluzioni al ne di ottenere la soluzione del problema dato. L'approccio generale può essere scritto così in pseudo-codice: DeI(P, n). n è la dimensione del problema P if n ≤ k then r ← soluzione diretta del problema return r else dividi il problema in sotto-problemi Pi ,..., Ph di dimensione n1 ,..., nh for i ← 1 to h do ri ← DeI(Pi , ni ) end for return combinazione di r1 ,..., rh 5  end if Per esempio, la ricerca binaria segue lo schema precedente: BinSearch-Ric(x, A, i, j ). Pre: A[i..j] ordinato. Post: true se x ∈ A[i..j] if i > j then return f alse else m ← b(i + j)/2c ifx = A[m] then return true else if x < A[m] then return BinSearch-Ric(x, A, i, m − 1) else. A[m] < x return BinSearch-Ric(x, A, m + 1, j) end if end if end if Nel caso peggiore (quando l'elemento cercato non è presente nel vettore), il tempo di esecuzione può essere espresso con la relazione  c se n=1 T (n) = n
T 2 +d se n>1 dove n è il numero di elementi del vettore (n = j − i + 1). Con il metodo dell'iterazione, assumendo che n è potenza di 2: n T (n) = T +d 2 n =T +d+d 4 dopo k ≤ log2 n iterazioni: n =T + kd 2k dopo k = log2 n iterazioni: = T (1) + d log2 n = c + d log2 n e quindi T (n) ∈ Θ(log n) Merge-sort. Ordinamento per fusione. L'idea: un vettore che contiene un elemento è ordinato; se il vettore contiene più di un elemento allora viene diviso in due parti bilanciate; ognuna di queste due parti viene ordinata applicando ricorsivamente l'algoritmo; le due parti vengono fuse. In pseudo-codice: Merge-Sort(A[1..n]) if n > 1 then m ← bn/2c 6  Merge-Sort(A[1..m]) Merge-Sort(A[m + 1..n]) Merge(A, 1, m, n) end if dove Merge(1, m, n) eettua la fusione di A[1..m] e A[m + 1..n] posto che essi sono ordinati. 7  L'algoritmo divide prima il vettore in sottovettori che contengono un solo elemento e poi tramite una sequenza di fusioni ordina tutto il vettore: 8 La fusione si può eettuare in maniera iterativa: Merge(A, f, m, l) i, j, k ← f, m + 1, 1 while i ≤ m ∧ j ≤ l do if A[i] ≤ A[j] then B[k] ← A[i] i←i+1 else B[k] ← A[j] j ←j+1 end if k ←k+1 end while if i ≤ m then B[k..k + m − i] ← A[i..m] else B[k..k + l − j] ← A[j..l] end if A[f, l] ← B[1..l − f + 1] dove f sta per rst, m per middle e l per last. Come precondizione si richiede che 1≤f ≤m≤l≤n (dove n è il numero di elementi in A) e che i sottovettori A[f, m] e A[m + 1, l] siano ordinati. La fusione può essere eettuata anche in maniera ricorsiva (l'algoritmo prende in input due vettori ordinati da fondere): Merge(B[1..nB ], C[1..nC ]) if nB = 0 then return C else if nC = 0 then return B else if B ≤ C then return [B, Merge(B[2..nB ], C)] else return [C, Merge(B, C[2..nC ])] end if end if ! end if Analisi della complessità del Merge-Sort. La fusione ha complessità temporale Θ(n). Di conseguenza, la complessità di Merge-Sort può essere descritta con la relazione di ricorrenza  a se n=1 T (n) = n
2T 2 + bn + c altrimenti 9 Con il metodo dell'iterazione: n T (n) = 2T + bn + c  2 n  n  = 2 2T + b + c + bn + c  n 4 2 = 4T + 2bn + 2c + c  4 n  n  = 4 2T + b + c + 2bn + 2c + c  n 8 4 = 8T + 3bn + 4c + 2c + c 8 dopo k ≤ log2 n iterazioni : n = 2k T + kbn + 2k−1 c + 2k−2 c + · · · + c 2k dopo k = log2 n iterazioni : n n = nT (1) + log2 n · bn + c + c + · · · + c 2 4 = na + log2 n · bn + (n − 1)c dove il termina dominante è bn log2 n e quindi la complessità temporale del Merge-Sort è T (n) ∈ Θ(n log n). Per quanto riguarda Quick-Sort, nel caso migliore, cioè quando il partizionamento divide in due parti uguali il vettore, la complessità è uguale a quella di Merge-Sort, quindi Θ(n log n). Per analizzare il caso medio del Quick-Sort, assumiamo che il partizionamento risulta in due parti che pos- sono essere sbilanciate in qualunque modo con la stessa probabilità. I casi per quanto riguarda la dimensione delle due parti sono (0, n − 1), (1, n − 2), (2, n − 3),... , (n − 2, 1), (n − 1, 0) e ognuno ha probabilità 1/n. Considerando tutti i casi con probabilità 1/n la relazione di ricorrenza diventa:  aP se n≤1 T (n) = 1 n n k=1 (T (k − 1) + T (n − k)) + bn + c altrimenti La ricorrenza può essere riscritta è manipolata n−1 2X T (n) = T (i) + bn + c n i=0 n−1 X nT (n) = 2 T (i) + bn2 + cn i=0 Sottraendo n−2 X (n − 1)T (n − 1) = 2 T (i) + b(n − 1)2 + c(n − 1) i=0 si ottiene n−1 ! n−2 ! X X nT (n) − (n − 1)T (n − 1) = 2 T (i) + bn2 + cn − 2 T (i) + b(n − 1)2 + c(n − 1) i=0 i=0 nT (n) − (n − 1)T (n − 1) = 2T (n − 1) + c + b(2n − 1) nT (n) = (n + 1)T (n − 1) + c + b(2n − 1) 10 dividendo a n(n + 1) T (n) T (n − 1) c + b(2n − 1) = + n+1 n n(n + 1) Introducendo D(n) = T (n)/(n + 1) abbiamo c + b(2n − 1) D(n) = D(n − 1) + n(n + 1) c+b(2n−1) dove n(n+1) ∈ O(1/n). Di conseguenza n ! X 1 D(n) ∈ O ∈ O(log n) i=1 i e quindi T (n) ∈ O(n log n) e quindi anche nel caso medio Quick-Sort è ottimale. Il seguente teorema, chiamato Teorema Master, fornisce una ricetta per trovare un limite superiore in senso O data una relazione di ricorrenza a partizioni bilanciate. Teorema: Siano a ≥ 1, b ≥ 2, c > 0, d, β ≥ 0 costanti intere non negative tale che  d se n = 1 T (n) = aT (n/b) + cnβ se n > 1 Posto α = log a/ log b T (n) ∈ O(nα ) se α>β α T (n) ∈ O(n log n) se α=β β T (n) ∈ O(n ) se α