Collection of solved exercises

Page 1

Esercizi risolti R1. Esercizio Sia dato il seguente problema: ordinare in ordine crescente gli elementi di una matrice di dimensioni n×m. Più precisamente, data una matrice M di n ×m elementi, gli elementi di M devono essere ridistribuiti in modo che, per ogni i=1, ..., n, per ogni j=1, ... m-1 si abbia M[i, j] ≤ M[i, j+1], ed inoltre, per ogni i=1, ..., n-1 deve essere M[i, m] ≤ M[i+1, 1]. Per esempio, la seguente matrice 2×3 5 1 9 13 2 6          viene modificata nella seguente matrice: 1 2 5 6 9 13          Si scriva un algoritmo che risolva il problema suddetto e se ne calcoli la complessità temporale. NB: si supponga pure che dato una matrice M, questa abbia un attributo height[M] che corrisponde al numero di righe della matrice, ed un attributo width[M] che ne rappresenta il numero di colonne. Si supponga inoltre che per accedere all'elemento di coordinate [i, j], la sintassi da usare sia M[i][j]. Soluzione Un possible algoritmo che risolve il problema dato è il seguente. Sort-Matrix (M) 1 crea un array A di lunghezza width[M]*heigth[M] 2 for i ← 1 to height[M] 3 do for j ← 1 to width[M] 4 do A[(i-1)*width[M]+j] = M[i][j] 5 MERGE-SORT(A) 6 for i ← 1 to height[M] 7 do for j ← 1 to width[M] 8 do M[i][j] = A[(i-1)*width[M]+j] La riga 1 richiede un tempo che è Θ(n*m). I cicli for delle righe 2-4 e 6-7 (che sono molto simili) richiedono entrambi un tempo Θ(n*m). La lunghezza dell'array A è uguale a n*m, per cui la complessità temporale del passo di MERGE-SORT è Θ(n*m*log(n*m)). La complessità globale dell'algoritmo SORT-MATRIX è quindi Θ(n*m)+Θ(n*m*log(n*m)), in cui il termine dominante è Θ(n*m*log(n*m)), che è quindi la complessità dell'algoritmo. Si noti inoltre che poichè log(n*m) = log(n)+log(m), la complessità è Θ(n*m*log(max(n,m))). Si noti…