[algoritmo] Esercizzio circa ordinamenti ed altro

[D4rkAng3l]

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:

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

[gugoXX]

L'esercizio DEVE avere complessita' O(N^2) o puo' anche essere minore?

O(N^2) e' davvero banale

A= array di x interi
B = array di y interi

RES = Lista Risultato;

FOREACH Aelem in A
{
     bool found=false;
     FOREACH Belem in B
     {
          if (Aelem==Belem)
          {
              found=true;
              break;
          }
     }
     if found Push Aelem in Lista;
}

Senza ordinare nulla, cercando ciascuno degli elementi di A dentro tutto B, anche non ordinato.

Casi da valutare sono quando in A o in B ci sono elementi ripetuti n,m volte. Cosa vorrebbe il prof.? Non l'ha scritto, e sono plausibili molte risposte.

Interessante sarebbe farlo in O(N), che e' possibile
Che e' anche la soluzione che C# sviluppa internamente nell'istruzione

  var Risultato=ListA.Intersect(ListB);

Dura la vita in C# eh?

Ricordati che ordinare costa caro. Ed e' utile ordinare solo quando successivamente ci si pone domande che coinvolgono < o >.
Fino a che si sta sull' = non e' quasi mai necessario/utile ordinare.

[D4rkAng3l]

Beh se la complessità è O(n^2) può anche essere minore in quanto f(n)=O(n^2) in realtà è un insieme di infinite funzioni tali che esistono 2 costanti c>0 ed n0>=0 tali che:

f(n) <= c*(n^2) Per ogni n>=n0

Quindi n=O(n^2)
10n*log(n)=O(n^2)
e così via...almeno credo...

[gugoXX]

Mmmh. Un conto e' la complessita' di un algoritmo, che dato un algoritmo e' sempre la stessa.
Un conto e' il tempo di elaborazione, dove occorre sostituire gli n, e dove le costanti sono importanti.

Un conto e' un esercizio che chiede la soluzione di un algoritmo in O(n^2), un altro e' chiedere la soluzione di un problema in tot millisecondi oppure in tot cicli macchina.

Comunque il prof. e' stato chiaro direi. Risolvi in O(n^2), senza ordinare, e sei a posto. E' semplicissimo.

Se invece vuoi strafare dicevo c'e' una soluzione O(n) (ovviamente senza ordinare)

[Furla]

Originariamente inviato da gugoXX

Se invece vuoi strafare dicevo c'e' una soluzione O(n) (ovviamente senza ordinare)

hash?
cmq non la postare assolutamente!