Confrontare due array in O(n), è possibile?

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 :sweat:, però se usi un unordered_map togli K

Poi ho testato le tre funzioni su 10^5 elementi:

  • O(N^2) 42 secondi
  • O(NlogN) 22 millisecondi
  • O(N) 1 millisecondo

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:

Comunque quello a cui mi riferivo era molto più semplice dell’unordered_map e garantisce \mathcal O(N), simile alla soluzione di @bortoz : Counting sort

1 Mi Piace

Dovrebbe essere \mathcal O, che ottieni scrivendo $\mathcal O$

1 Mi Piace

Il counting sort non funziona solo con intervalli piccoli?

La mia soluzione funziona fino a K ≤ 10^6.
La differenza rispetto al Counting Sort è che in quest’ultimo devi controllare tutti i valori da 0 a K-1. Mentre in questo caso devi solo controllare i valori di A.

In questo caso i valori vanno da 0 a 25 sottraendo la “a” ad ogni carattere

Sei rimasto un po’ indietro direi :joy:

Perché? Stavo rispondendo al fatto che il counting sort funziona con soli valori piccoli e in questo caso i valori vanno da 0 a 25

Hai ragione ma non stavamo più parlando di Las Vegas.
Comunque spero che queste implementazioni soddisfino la tua domanda.

Adesso guardo meglio le funzioni e magari cerco un algoritmo che può essere implementato sugli array anche solo per vedere dove sta il risparmio di tempo :smile:

Grazie mille comunque!!:blush:

Per confrontare in O(N) due vettori A e B lunghi N si può fare qualche magheggio con gli Hash. Diciamo che K è un numero piccolo e costante, ed abbiamo K funzioni f_1,f_2,\ldots,f_K, che prendono in input un elemento del vettore e ritornano un intero. È meglio sceglierle abbastanza varie, e che possano essere calcolate in O(1). Per ogni diversa f_i, confrontiamo f_i(A_1)+f_i(A_2)+\ldots+f_i(A_N) con f_i(B_1)+f_i(B_2)+\ldots+f_i(B_N), f_i(A_1)\oplus f_i(A_2)\oplus \ldots \oplus f_i(A_N) con f_i(B_1)\oplus f_i(B_2)\oplus \ldots \oplus f_i(B_N), f_i(A_1)\cdot f_i(A_2)\cdot \ldots \cdot f_i(A_N) \mod p con f_i(B_1)\cdot f_i(B_2)\cdot \ldots \cdot f_i(B_N) \mod p. Se ogni confronto ci dà esito positivo, dobbiamo concludere che è molto molto molto molto probabile che A = B. La complessità è quindi O(N \cdot K), ma essendo K costante sarà O(N).
Ovviamente non possiamo essere certi del risultato, per essere certi dobbiamo accettare un algoritmo O(N \log N). In fondo il senso dell’hashing Montecarlo è evitare confronti lunghi dando risposte di cui si è quasi sicuri, facendo un compromesso tra velocità è sicurezza. La maggior parte delle volte funziona.

Guardando un po’ in giro ho trovato questa guida dove a pagina 245 credo sia descritto questo argomento.

Parla dell’hashing polinomiale. Due array con gli stessi elementi in ordine diverse hanno diverso Hash polinomiale

Allora probabilmente non so leggere :joy:

Ma sfugge qualcosa a me oppure se la somma dei valori dei vettori a e b ha lo stesso risultato anche la somma delle funzioni avrò tutte lo stesso risultato:
Escludendo che le funzioni eseguono solo una moltiplicazione altrimenti ovviamente se a e b hanno come somma s_a = s_b anche s_a*k==s_b

Ma anche aggiungendo delle somme:
A: 2 3 5 s_a=10
B 0 5 5 s_b=10
con:

int f1(int val)
{
return (val*3)+1;
}
int f2(int val)
{
return (val+1)*3;
}

s_f1 su a 7+10+16=33
s_f1 su b 1+16+16=33

s_f2 su a 9+12+18=39
s_f2 su b 3+18+18=39

E cosi via per ogni funzione f_i alla fine non equivale fare la somma e poi applicare la funzione sulla somma, e quindi nel caso in cui la somma sia uguale anche la somma delle funzioni risulta uguale

usando le f_1 ed f_2 definite da te, basta che i due vettori abbiano la stessa somma. Se invece mettiamo f_2(n) = n^2, non tutti i vettori con la stessa somma avranno stessa \sum\limits_{i=1}^N f_2(V_i).