Solo quisiera hacer la anotación siguiente:
En caso de ocupar dos ciclos for, la complejidad es O(nm)
, n
siendo la longitud del primer arreglo y m
la longitud del otro.
Aunque no lo parezca si utilizas funciones de javascript como indexOf
, filter
, some
, etc... y tú solo estás escribiendo un for, aún así el algoritmo tiene complejidad O(nm)
pues estos métodos tienen complejidad lineal, internamente escanean el arreglo hasta encontrar el elemento.
Si es importante el performance, quizá deberías usar un algoritmo (u otro lenguaje) con mejor comportamiento asintótico.
Yo propongo primero ordenar el arreglo que tenga más elementos, que tomaría tiempo O(nlog(n))
y después iterar sobre el arreglo que tenga menos elementos y hacer binary search con el arreglo que tenga más elementos, que tomaría tiempo O(mlog(n))
. Esto obviamente en términos de complejidad sería más conveniente, pero quizá no sea lo que se desee, en cualquier caso el orden se podría intercambiar.
Probablemente en javascript no se note la diferencia entre linear search y binary search, o quizá inclusive esto sea contradictorio pues actualmente JS no tiene implementado binary search de forma nativa, a diferencia de indexOf
o las funciones ya mencionadas y como es un lenguaje interpretado inclusive podría llegar a ser contraproducente hacer binary search, o tal vez las ganancias de performance se noten cuando tienes muchísimos elementos. Pero si eso llegara a pasar, entonces quizá no sería cosa del algoritmo utilizado, sino del lenguaje.
En fin, era algo que quería comentar, espero a alguien le sirva de algo.