[Algoritmi, Java] Esercizio su array

[giorgia.compagno]

Buongiorno a tutti!
Vorrei chiedervi qualche consiglio sul seguente esercizio di cui riporto il testo.

Siano A e B due array validi, di lunghezza positiva, contenenti numeri interi. I due array,
A e B, sono (entrambi) ordinati in senso crescente. Sia n = A.length + B.length.
Progettare e descrivere un algoritmo che, con prestazioni temporali asintotiche O(n log n),
calcoli quante sono le coppie (a, b[j]), con a appartenente ad A, b[j] appartenente a B, a > b[j], i < j.
Se lo si ritiene utile, si può ipotizzare che gli elementi complessivamente contenuti nei due
array siano tra loro tutti distinti.
L’algoritmo NON può modificare il contenuto degli array A e B e può utilizzare strutture
dati aggiuntive (la cui natura e il cui utilizzo va descritto in dettaglio), cercando comunque
di minimizzare l’occupazione di memoria.
Implementare l’algoritmo in Java, con un metodo statico avente questa firma (senza
verificare le pre-condizioni):
public static int count(int[] a, int[] b)

Lasciando un attimo perdere l'implementazione in java, la mia idea di soluzione (in una specie di pseudocodice) è questa:

i=0, j=B.length-1, count=0
while (i<max(A.length,B.length))
         if (a[i]<b[j])
                j--
         else 
                count = count + (j-i)
                i++
                j = B.length-1

Ho fatto qualche prova "a mano" e mi sembra che funzioni (ma potrebbe anche essere sbagliato). Il mio dubbio è, nell'ipotesi che questo algoritmo faccia veramente quello che deve fare, quali sono le prestazioni? C'è un unico ciclo che, al massimo, viene eseguito n-1 volte (infatti, al massimo, uno dei due array ha dimensione 1) e viene eseguito in media n/2 volte. Ma può essere che le prestazioni siano "solo" O(n)? O sto tralasciando qualcosa?

Vi ringrazio in anticipo per l'aiuto

[milizia96]

Nella terza riga il < dovrebbe essere un <= ? Inoltre aggiungerei qualche controllo per evitare che j diventi negativo.

Prova a vedere quante volte viene eseguito il ciclo se gli elementi di A sono tutti minori di ogni elemento di B, se non mi sbaglio in questo caso il numero di operazioni sarà quadratico in n.

[Cronovirus]

Se l'algoritmo che hai scritto risolve il tuo problema allora è addirittura meno di $O(n-1)$. Da quello che hai scritto

 n = A.length + B.length

e il tuo ciclo va da i = 0 a

i<max(A.length,B.length)

Ahimè max(A.length,B.length) <= n

[giorgia.compagno]

Si dovrebbe essere <= e avevo pensato ad un controllo su j che non ho messo perché non modifica le prestazioni, che effettivamente sono quadratiche nel caso che riporti tu. Quindi non va bene.

Cronovirus intendevo "solo" O(n) nel senso che se di solito se un problema dà un certo vincolo sulle prestazioni (in questo caso era O(nlogn)) vuol dire che è difficile riuscire a farlo con prestazioni migliori, per questo mi sembrava di aver trascurato qualcosa.

Inizialmente avevo pensato di usare una strategia tipo merge sort, e in effetti è quella la strategia che si usa se si devono contare le inversioni in un unico array, come in questo problema (simile).

Dato un array A di n valori distinti appartenenti a un
insieme totalmente ordinato (secondo la relazione
simbolicamente indicata "≤"), una coppia di suoi
elementi, A e A[j], è una inversione se e solo se
A ≤ A[j] e i > j.

Però qui si copia l'array in un altro array, si partiziona ricorsivamente e si ordina come in mergesort (tenendo conto delle inversioni eventualmente presenti all'interno delle singole partizioni prima dell'ordinamento) e poi si modifica la funzione merge in modo che tenga conto delle inversioni tra le due partizioni.
Immagino che ci sia un modo per modificare leggermente questo algoritmo in modo che valga anche per l'esercizio che ho riportato io, ma non capisco dove dovrebbe saltar fuori la parte O(nlogn), che nel merge sort è data dalle ricorsioni per l'ordinamento, visto che io nel mio esercizio dispongo di due array separati e già ordinati.

[Cronovirus]

"giorgia.compagno":Si dovrebbe essere <= e avevo pensato ad un controllo su j che non ho messo perché non modifica le prestazioni, che effettivamente sono quadratiche nel caso che riporti tu. Quindi non va bene.

Cronovirus intendevo "solo" O(n) nel senso che se di solito se un problema dà un certo vincolo sulle prestazioni (in questo caso era O(nlogn)) vuol dire che è difficile riuscire a farlo con prestazioni migliori, per questo mi sembrava di aver trascurato qualcosa.

Inizialmente avevo pensato di usare una strategia tipo merge sort, e in effetti è quella la strategia che si usa se si devono contare le inversioni in un unico array, come in questo problema (simile).

Dato un array A di n valori distinti appartenenti a un
insieme totalmente ordinato (secondo la relazione
simbolicamente indicata "≤"), una coppia di suoi
elementi, A e A[j], è una inversione se e solo se
A ≤ A[j] e i > j.

Però qui si copia l'array in un altro array, si partiziona ricorsivamente e si ordina come in mergesort (tenendo conto delle inversioni eventualmente presenti all'interno delle singole partizioni prima dell'ordinamento) e poi si modifica la funzione merge in modo che tenga conto delle inversioni tra le due partizioni.
Immagino che ci sia un modo per modificare leggermente questo algoritmo in modo che valga anche per l'esercizio che ho riportato io, ma non capisco dove dovrebbe saltar fuori la parte O(nlogn), che nel merge sort è data dalle ricorsioni per l'ordinamento, visto che io nel mio esercizio dispongo di due array separati e già ordinati.

Beh l'algoritmo l'hai scritto e per eseguirlo in java ci metti 5 minuti. Puoi verificarne la correttezza immediatamente. Quindi la tua domanda è come si fa o la complessità in tempo dell'algoritmo che hai proposto come soluzione?

[giorgia.compagno]

La prima domanda era qual era la complessità asintotica dell'algoritmo che avevo proposto, che ho appurato essere quadratica (in effetti non ci voleva molto, ma quella che mi ha suggerito milizia96 è l'unica prova che stupidamente non avevo fatto).
Appurato quindi che l'algoritmo non risolve il mio problema con i vincoli che ho, ho condiviso la seconda idea semplicemente per avere qualche opinione o consiglio a riguardo.

[onlyReferee]

Ciao Giorgia
Secondo me conviene provare a modificare in base alle nostre esigenze la procedura merge dell'algoritmo di ordinamento merge-sort, dato che la complessità totale dell'algoritmo è $O(n \log n)$ e nel nostro caso abbiamo due sequenze di elementi già ordinate (seppur di dimensione diversa). Ovviamente ci serve anche un array di supporto in cui andranno inseriti in maniera ordinata gli elementi dei nostri due array di input $A$ e $B$.
Intanto provo ad impostarlo anche io, se mi vengono in mente altre delucidazione ti faccio sapere.
Spero intanto di esserti stato d'aiuto.