Esercizi svolti di informatica n.5

Dati due insiemi di interi A=a₁, a₂, …, a_ne B=b₁, b₂, …, b_m, sia C la loro intersezione, ovvero l’insieme degli elementi contenuti sia in A che in B.

Si discuta, confrontandola, la complessità computazionale dei seguenti due approcci al problema:

• applicare un algoritmo “naive” che confronta elemento per elemento;
• applicare un algoritmo che prima ordina gli elementi di A e B.

SOLUZIONE.

La soluzione “naive” è la prima e più semplice che viene in mente: per ogni elemento di A (cioè FOR un certo indice i che va da 1 ad n) si scorre B (cioè FOR un certo altro indice j che va da 1 ad m) per vedere se l’elemento a_i è presente o no. Ne segue che la complessità di questo approccio è O(nm). Scriviamo O e non perché, mentre il ciclo FOR i viene eseguito completamente, il ciclo FOR j si interrompe appena l’elemento a_iè uguale all’elemento b_j. Pertanto, nel caso migliore, in cui tutti gli elementi di A sono uguali tra loro ed al primo elemento di B la complessità è (n), ma nel caso peggiore, in cui l’intersezione è vuota, la complessità è (nm). Tra l’altro, l’analisi del caso migliore fa venire in mente che una trattazione a parte meriterebbe il caso della duplicazione degli elementi; esso si risolve facilmente ricordando che un insieme, per definizione, non ammette ripetizioni al suo interno, e quindi dobbiamo considerare gli a_i tutti distinti tra loro, così come i b_i. Ne discende che il caso migliore presentato non è ammissibile, ma questo non cambia la complessità del caso peggiore.

Consideriamo ora il secondo approccio: si ordinino gli insiemi A e B in modo crescente, e poi si confrontino alla maniera, per capirsi, dell’operazione Merge del merge-sort (si pongano un indice i all’inizio di A e un indice j all’inizio di B; si confronti A[i]con B[j]: se essi sono uguali l’elemento si inserisce in Ce si incrementano sia i che j, se A[i] è minore si incrementa i, se B[j] è minore si incrementa je si ripeta dal confronto finché non si raggiunga la fine di uno dei due vettori). La complessità T(n,m) di questo approccio deve tener conto della complessità dell’ordinamento e della complessità del confronto, e pertanto è pari a (n log n)+(m log m)+(max(n,m)); se assumiamo, senza perdere di generalità, che n>m si ha che T(n,m)=(n log n)+(n)=(n log n). Se possiamo fare alcune ipotesi sugli elementi di A e di B, in modo da poter applicare uno degli algoritmi di ordinamento lineari, la complessità si abbassa ulteriormente a (n).