Ragazzi scusate se rompo ma tra 3 giorni ho l'esame di elementi di algoritmi e strutture dati e sono molto preoccupato...ho questo esercizio proposto su un vecchio compito d'esame.
ESERCIO:
Siano A = {a1, a2, ...., an} e B = {b1, b2, ...., bn} due insiemi di interi.
Si realizzi un algoritmo che, preso in input i due insiemi memorizzati in due array, restituisce la loro intersezione, cioè l'insieme composto da tutti gli elementi che sono sia in A che in B. L'algoritmo deve avere complessitµa temporale o(n^2).
Attenzione: l'esercizio sarà valutato solo se corredato da adeguata descrizione del funzionamento dell'algoritmo, in base ai seguenti parametri: correttezza, efficienza e analisi di complessità.
La mia soluzione è la seguente:
A e B sono due array di interi e devo realizzare un algoritmo che mi metta in un altro array C i valori appartenenti sia ad A che a B (appunto l'intereszione dei due array di input) in un tempo che sia o(n^2) quindi avente come complessità temporale una funzione g(n) che cresca in maniera strettamente minore di f(n)=n^2
Intanto credo che dati i due vettori A e B il modo più rapido per determinarne l'interesezione lo posso trovare se A e B sono ordinati. Quindi inizialmente ordino i miei due vettori A e B con l'algoritmo di ordinamento per confronti più veloce che conosco che è l'heapsort che ha una complessità pari ad O(n*log(n)) il che non mi causa problemi perchè non mi fa sforare dall'estremo superiore impostomi.
Poi per trovare i valori comuni ai due vettori faccio nel seguente modo:
Imposto un indice di scorrimento per A che chiamerò begin_A, un indice di scorrimento per B che chiamerò begin_B ed un indice di scorrimento del vettore contenitore C che chimaerò semplicemente i.
All'inizio begin_A e begin_B sono impostati sulla prima locazione di A e B.
Eseguo una serie di confronti finchè entrambi i vettori A e B sono completamente consumati.
Se il valore di A in posizione begin_A è uguale al valore di B in posizione begin_B metto quel valore nell'array C ed incremento entrambi gli indici.
Se il valore di A in posizione begin_A è minore del valore di B in posizione begin_B incremento begin_B, vicerversa avrei incrementato begin_A e continuato ad eseguire i confronti.
In pseudocodice credo sia qualcosa del tipo:
Codice:
A= array di x interi
B = array di y interi
C = array di min{x, y} // Perchè al massimo potranno avere in comune tutti gli elementi dell'array più piccolo
begin_A = 0
begin_B = 0
i = 0
WHILE(begin_A != x and begin_B !=y){
IF(A[begin_A] == B[begin_B]) THEN{
C[i] = A[begin_A] //Copia l'elemento comune in C
INCREMENTA begin_A di 1
INCREMENTA begin_B di 1
}
ELSE IF A[begin_A] < B[begin_B] THEN
INCREMENTA begin_A di 1
ELSE
INCREMENTA begin_B di 1
}
Questo sistema dovrebbe essere il sistema usato dal mergesort e dovrebbe avere una complessità temporale O(n) perchè credo che nel caso peggiore il numero di confronti effettuato sia <=2n
Quindi la complessità totale di tutto l'algoritmo incluso l'ordinamento mediante heapsort dovrebbe essere O(n*log(n)) che è un o(n^2)
mmm dite che ci può stare? magari non del tutto (ammetto di non mirare al 30 a sto esame doh
).
L'esercizio valeva 8 punti...quanti me ne avreste dati?
Grazie
Andrea