Curso 2023/2024
Sean a la talla del vector A y b la talla del vector B.
Sabemos que podemos ordenar eficientemente un vector de talla n en tiempo O(n log n), por ejemplo empleando mergesort o heapsort. Si no nos permiten modificar el vector dado, podemos ordenar una copia.
Sabemos que b ≤ a porque todos los elementos de B están en A, tendremos en cuenta eso al elegir el termino dominante del coste.
Podemos considerar 4 soluciones:
Sin ordenar ninguno de los dos vectores, podemos hacer una búsqueda secuencial en B de cada elemento de A.
Coste temporal: O(a b).
Ordenando solamente el vector B, podemos hacer una búsqueda binaria en B de cada elemento de A. Nos interesan los de A que no encontremos.
Coste temporal: O(b log b + a log b) = O(a log b).
Ordenando solamente el vector A, podemos hacer una búsqueda binaria en A de cada elemento de B. Nos interesan los de A que no encontremos, para lo cual podemos ir marcando los que encontremos añadiendo un atributo booleano a los elementos de A o utilizando un vector auxiliar de booleanos de talla a.
Coste temporal: O(a log a + b log a + a) = O(a log a).
Ordenando ambos vectores, podemos recorrer ambos con coste lineal para averiguar cuáles son los elementos de A que no están en B, como hemos visto en otros problemas similares (por ejemplo, el de la mezcla de dos vectores ordenados).
Coste temporal: O(a log a + b log b + a + b) = O(a log a).
De estas 4 soluciones, la de menor coste es la segunda. Interesa, por tanto, ordenar solamente el vector B.
Podemos considerar dos soluciones de las cuatro anteriores:
Sin ordenar B y aprovechando que A está ordenado, el coste temporal es O(b log a + a).
Ordenando B y aprovechando luego que A y B están ordenados, el coste temporal es O(b log b + a + b) = O(b log b + a).
De estas dos soluciones, la de menor coste es la segunda. Interesa, por tanto, ordenar el vector B.
Análogamente, podemos considerar dos soluciones de las cuatro del caso 1:
Sin ordenar A y aprovechando que B está ordenado, el coste temporal es O(a log b).
Ordenando A y aprovechando luego que A y B están ordenados, el coste temporal es O(a log a + a + b) = O(a log a).
De estas dos soluciones, la de menor coste es la primera. No interesa, por tanto, ordenar el vector A.
En este caso, lo eficiente es aprovechar que ambos están ordenados para resolver el problema en tiempo O(a + b) = O(a).
¿Sería correcto decir que el coste es O(b log a) en el caso 2.1 y O(b log b) en el caso 2.2, por ser esos los terminos dominantes?
Respuesta: no podemos hacer esa simplificación sin saber cuánto vale b. Esto se ve considerando estas dos situaciones extremas:
si b vale 1:
En el caso 2.1 queda O(b log a + a) = O(a).
En el caso 2.2 queda O(b log b + a) = O(a).
si b vale a:
En el caso 2.1 queda O(b log a + a) = O(a log a).
En el caso 2.2 queda O(b log b + a) = O(a log a).