Cambio de representación en la técnica Transfer and Conquer

El cambio de representación es una de las variantes de la técnica Transfer and Conquer donde el problema dado se transforma en otro dominio que es más familiar o más simple de ejecutar. En el caso de cambio de representación, la instancia de un problema dado se transforma en otra representación sin afectar la instancia original.

Características: 

A continuación se presentan algunas características básicas de la técnica de Cambio de Representación:

• Solo se cambia la representación de la instancia, pero se debe conservar la instancia original. 
• La extracción del resultado de la nueva representación debería ser más eficiente que la original.

Ejemplo:

Entendamos mejor el cambio de representación con la ayuda de un ejemplo:

Considere el problema Encontrar si hay algún elemento duplicado en la array

Enfoque 1: para resolver este problema, se puede comparar cada elemento con todos los demás elementos de la array y encontrar si hay algún duplicado presente en la array o no.

Se puede escribir de la siguiente manera:

• Iterar un bucle desde el principio hasta el final
  • Compara cada elemento con todos los demás elementos.
  • Si hay una coincidencia, entonces existe un duplicado.
  • De lo contrario, no se encuentra ningún duplicado para el elemento actual.
• En última instancia, después de recorrer todos los elementos y no encontrar ningún duplicado en ninguna iteración, la array no contiene un valor duplicado.

Algoritmo:

Algoritmo find_duplicate(A[1, 2, . . . N]):
        para i = 0 a N-1:
                temp = A[i]
                para j = i+1 a N:
                        temp1 = A[j]
                        si temp == temp1:
                                duplicado encontrado
                        final si
                final para
        final para

Complejidad de Tiempo: O(N ² )
Espacio Auxiliar: O(1)

Enfoque 2 (Cambio de Representación): El problema anterior es complejo en el sentido de la comparación. Requiere muchas comparaciones. Esta complejidad se puede reducir como se muestra a continuación:

• Cambie la array anterior a un árbol rojo-negro que contendrá solo elementos únicos (la funcionalidad se implementa en un conjunto).
• Si el tamaño del árbol y la array son iguales, entonces no hay duplicado.

Esta es la técnica de cambio de representación donde se cambia la representación de la array y el problema se resuelve de manera eficiente.

El enfoque es el siguiente:

• Construya un conjunto vacío (que implemente el árbol rojo-negro).
• Inserte los elementos de la array en el conjunto.
• Si el tamaño del conjunto y el tamaño de la array son iguales, no hay duplicado. De lo contrario, hay elementos duplicados.

Algoritmo:

Algoritmo find_duplicate(A[1, 2, . . . N]):
        establezca st[]
        para i = 0 a N:
                inserte A[i] en st[]
        end for
        if sizeof(st) == N:
                sin duplicado
        más :
                el duplicado existe
        finaliza si

Complejidad de tiempo: O (N * logN) que se requiere para insertar todos los elementos de la array en el conjunto.
Espacio Auxiliar: O(N) 

Ventajas: Las ventajas del método de cambio de representación se mencionan a continuación

• Al cambiar la representación, la complejidad temporal del problema se reduce en gran medida.
• La instancia del problema dado se conserva después de cambiar su representación. 

Desventajas: También hay algunas desventajas de la técnica como:

• Construir una nueva instancia del problema dado es difícil y costoso.