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:
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
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.
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
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.
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 5s_a=10 B 0 5 5s_b=10
con:
int f1(int val)
{
return (val*3)+1;
}
int f2(int val)
{
return (val+1)*3;
}
s_f1 su a7+10+16=33 s_f1 su b1+16+16=33
s_f2 su a9+12+18=39 s_f2 su b3+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).