EFICIENCIA DEL MÉTODO

Normalmente, esta técnica proporciona una forma natural de diseñar algoritmos eficientes. Por ejemplo, si el trabajo de dividir el problema y de combinar las soluciones parciales es proporcional al tamaño del problema (n); tenemos un número limitado p de subproblemas de tamaño aproximadamente igual a n/p (porque el algoritmo se va dividiendo) en cada etapa; y por último, los casos base requieren un tiempo constante en (O(1)); entonces el algoritmo divide y vencerás tiene por cota superior asintótica a O(n log n). Esta cota es la que tienen los algoritmos divide y vencerás que solucionan problemas tales como los de ordenamiento y la transformada discreta de Fourier.

En general, para determinar la eficiencia de los algoritmos divide y vencerás, se utiliza el siguiente criterio:

T(n) = aT(n/b) + f (n) donde f (n)∈O(n^k)
1.Si a < b^k              T(n) ∈ O(n^k)
2.Si a = b^k              T(n) ∈ O(n^k * lg n )
3.Si a > b^k              T(n) ∈ O(n^logb a)

Veamos un ejemplo:

T(n) = 4T(n/2) + n^2 y T(1) = 1.

En este ejemplo: a = 4, b = 2 y k = 2, entonces notamos que a = b^k, es decir, 4 = 2^2

por lo que, usando el segundo criterio, concluimos que la eficiencia del algoritmo es:

T(n) ∈ O(n^2 * lg n )

Ejercicios:

1.- Responde: La búsqueda binaria, ¿usa la estrategia divide-y-vencerás?

2.- Para multiplicar directamente dos números de n bits u y v se requieren O(n^2) pasos. Al aplicar el método divide-y-vencerás, el número puede separarse en dos partes iguales y calcular el producto aplicando el método siguiente:


uV = (a • 2^(n/2) + b) • (c • 2^(n/2) + d) = ac • 2^n + (ad + bc) • 2^(n/2) + bd.

Si ad + be se calcula como (a + b) (c + d) - ac - bd, ¿cuál es el tiempo cálculo?

 

3.- Sea T (n) = b para n=1 y a la vez, T(n) = aT(n/c) + bn , donde a, b y c son constantes no negativas. Demuestre que si n es una potencia de c, entonces:


T(n) = O(n) si a < c

T(n) = O(n loga n) si a=c

T(n) = O(n^logc a) si a>c

 

4.- Demuestre que si T(n) = mT(n/2) + an^2, entonces T(n) es satisfecho por:

 

T(n) = O(n^log m) si m > 4

T(n) = O(n^2 * log n) si m =4

T(n) = O(n^2) si m<4

 

5.- Diseñe un algoritmo con tiempo O(n log n) para encontrar la subsecuencia monótona creciente más larga de una secuencia de n números.