Algoritmos y Estructuras de Datos - VJ1215

Solución del ejercicio 14 del tema 1

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.

Caso 1: si ninguno de los dos vectores está ordenado

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.

Caso 2: si el vector `A` ya está ordenado y el `B` no

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.

Caso 3: si el vector `B` ya está ordenado y el `A` no

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.

Caso 4: si los vectores `A` y `B` ya están ordenados

En este caso, lo eficiente es aprovechar que ambos están ordenados para resolver el problema en tiempo O(a + b) = O(a).

Pregunta de un estudiante

¿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).