Capítulo 8. Divide y Conquista (Parte IV)

En este capítulo veremos un nuevo ejemplo de aplicación de la técnica de DyC.

 

Problema

Sea A[1...n], n >= 1, un vector de enteros diferentes y ordenados crecientemente, tal que algunos de los valores pueden ser negativos. Diseñar un algoritmo que devuelva un índice natural k, 1 <= k <= n, tal que A[k] = k, siempre que tal índice exista.

Pseudocódigo



 

La letra C significa que ese bloque tiene una complejidad temporal constante.

 

Análisis de complejidad Temporal

Vemos que el tamaño de la entrada se reduce a la mitad, por lo tanto nos encuadramos en el Caso 2

 

a = 1

b = 2

k = 0

 

Notar que 'a' es igual a 1 porque nunca se ejecutan ambos bloques (si uno se ejecuta, el otro no)

 

Reemplazando estos valores de los parámetros el costo del método queda en O(log n)

 

En este ejemplo, pusimos como pre condición, que el vector de enteros estuviera ordenado en forma creciente. En los próximos capítulos veremos métodos de ordenamiento que utilizan la técnica de Divide y Conquista para ordenar una cadena.