Buonasera, stavo analizzando questo quesito: Dati due array A e B di dimensione n quale è la complessità minore per capire se i due array contengono gli stessi numeri (anche in posizioni differenti)
La soluzione più semplice é quella di ordinare gli array (n\log_2 n) e confrontare poi A[i]==B[i] per i_0, i_1...i_n
Stavo pensando come ottenere la stessa soluzione in complessità O(n) ed avevo pensato di confrontare la somma dei valori di A[i] per i_0, i_1...i_n con quella di di B[i] per i_0, i_1...i_n e fare lo stesso ragionamento con il prodotto, ipotizzando che data una somma s ed un prodotto p esista una sola sequenza di n valori che la possa produrre(che corrisponde ad A e B)
Introducendo anche un +1 sui valori ( se positivi ) in quanto lo 0 possa falsare il prodotto
A=0 0 0 4;
B= 1 2 1 0;
Senza la modifica risulterrebbero “uguali”
Il problema si è creato nel testare la mia soluzione in quanto io abbia usato Las Vegas come esempio(sono a conoscenza del fatto che per la risoluzione del problema non basta che i valori, in questo caso caratteri, siano uguali ma devono avere anche un certo ordine, ma ho notato qui che l’ordine non risulta necessario per i testcase proposti ) ma non riesco ad ottenere 100/100 e voglio capire se ho sbagliato ad implementarlo oppure non è vero che data una somma s ed un prodotto p esista una sola sequenza di n valori che la possa produrre(che corrisponde ad A e B)
Questa è l’implementazione che ho provato usando i char(Un fattore che mi lascia perplesso è che sottraendo 97 ai char sbaglio solo un caso mentre sottraendo 96, che rispetta quello che ho detto prima sul +1 ne sbaglia molti)
Qualche aiutino?Spero di non aver compiuto errori imbarazzanti nei codici
Per confrontare due array puoi usare la funzione is_permutation della libreria <algorithm> che però ha complessità O(N^2).
Invece per somma e prodotto, per N=2 è sempre vero poiché dati somma s e prodotto p, i due numeri sono le soluzioni dell’equazione di secondo grado x^2 - sx + p = 0, per N>2 non ne ho idea.
Poi ho notato che nella tua implementazione scrivi sommaA = sommaA%1000000007 quando basterebbe sommaA %= 1000000007 ma questo è un piccolo dettaglio
Ho verificato su Las Vegas con questo codice fatto al volo e ho ottenuto 100/100.
int N;
in >> N;
vector<char> G(N);
vector<char> S(N);
for (int i=0; i<N; i++)
in >> G[i];
for (int i=0; i<N; i++)
in >> S[i];
out << is_permutation(G.begin(),G.end(),S.begin());
Non la conoscevo, ma come detto prima si può ancora abbassare con le sort()[quote=“bortoz, post:2, topic:4718”]
Invece per somma e prodotto, per N=2N=2N=2 è sempre vero poiché dati somma sss e prodotto ppp, i due numeri sono le soluzioni dell’equazione di secondo grado x2−sx+p=0 [/quote]
Proprio per questo motivo avevo pesatto a questa soluzione😀
Si chiama notazione O grande per un motivo
Non vorrei dire stupidate ma mi sembra che O indica per il caso peggiore, Ω il caso ottimale e Θ il caso medio (scusatemi se sbaglio).
Suggerimento: si può confrontare due array di tipo T in O(n) usando una unordered_map<T,int> che garantisce, se le cose vanno bene, accesso in O(1).
AGGIUNTA: se T è un tipo intero e i numeri negli array sono tutti positivi e “piccoli” al possto unordered_map<T,int> si può usare un array di int di dimensione max(val+1) dove val è il valore più grande che potremmo trovare nei due array.
Accedere ad un elemento in un unordered_map ha come caso medio Θ(1) che ripetuto per N volte diventa Θ(N).
Non essendo ordinato per accedere ad un elemento il caso peggiore non è O(logN) (che invece troviamo nelle map) ma bensì O(N) che diventa O(N^2) se lo ripeti per N volte.
Tuttavia nella maggior parte dei casi gli unordered_map risultano affidabili con tempi piuttosto buoni.
Implementazione in O(N) che funziona con un intervallo K≤10^6:
bool my_is_permutation(int N, int K, int A[], int B[])
{
vector<int> freq(K,0);
for (int i=0; i<N; i++)
freq[A[i]]++;
for (int i=0; i<N; i++)
freq[B[i]]--;
for (int i=0; i<N; i++)
if (freq[A[i]])
return false;
return true;
}
Non ho capito la parte dopo “Non essendo ordinato”.
template<typename T>
bool my_is_permutation(int N, int K, T A[], T B[])
{
unordered_map<T,int> freq;
freq.reserve(N);//Assai opzionale
for (int i=0; i<N; i++)
freq[A[i]]++;
for (int i=0; i<N; i++)
freq[B[i]]--;
for (int i=0; i<N; i++)
if (freq[A[i]])
return false;
return true;
}
Così dovrebbe avere complessità O(n).
P.S.: scusa se ho copiato il tuo codice.
Semplicemente il caso peggiore per accedere ad un elemento è O(N), questa operazione la dobbiamo ripetere N volte e quindi la complessità finale viene O(N^2), ma viene spesso aprrossimata a Θ(N).
Fa pure, non è ancora arrivato il giorno in cui venderò algoritmi , però se usi un unordered_map togli K
Perché il caso peggiore per accedere ad un elemento sarebbe O(n)?
Ciò con unordered_map e unirdered_set accade solo se per sfortuna è necessario il rehashing di tutti gli elementi cosa che si può scongiurare usando reserve e qualche altro “trucchetto”.
Non so bene il perché ma da quel che mi avevano spiegato degli unordered_map il caso medio è Θ(1) mentre il caso peggiore è O(N). Poi ho guardato anche qua dove c’è scritto:
Complexity
Average case: constant.
Worst case: linear in container size.
May trigger a rehash if an element is inserted (not included in the complexity above).
Allora, il rehashing può capitare ma se si riserva abbastanza spazio in memoria diventa improbabile.
Inoltre nell’algoritmo sopra lo si può rendere impossibile nel secondo ciclo, usando un controllo come:
if (freq.find(B[i])!=freq.end())
–freq[B[i]];
else
return false;
mentre che il rehash avvenga nel terzo ciclo è già impossibile.
Prova a usare freq.reserve(N*2), questo dovrebbe scongiurare il rehash.
Mi fido di uno che ha più esperienza di me.
Comunque credo che hai capito male, l’algoritmo che ho testato in O(N^2) era la funzione is_permutation della libreria <algorithm>, quella in O(N) era quello che ho scritto io, la tua versione che usa un unordered_map non l’ho testata ma credo che abbia prestazioni simili a quella O(N) ∼ 1 ms.
Se vuoi ti lascio il codice dei programmi che ho usato per testare:
, però se usi un