Div y Conquista: Teorema Maestro

Question 1

¿Qué es “División y Conquista”?
¿Qué se requiere para analizar su complejidad?

Answer 1

Es un conjunto de técnicas algorítmicas:

• Se divide el problema en subproblemas de igual naturaleza y menor tamaño.
• Se los conquista (resuelve) de forma recursiva hasta un caso base.
• Se combinan los resultados en una solución general.

Analizar su complejidad requiere resolver una relación de concurrencia.
Para esto, vamos a desarrollar el cálculo de la complejidad temporal en cada nivel de recursión y luego sumar los tiempos requeridos en cada uno para obtener el tiempo total de ejecución del algoritmo.

Question 2

¿Cuál es la plantilla básica de división y conquista?

Answer 2

1. Dividir el problema en q subproblemas de tamaño reducido al original.
2. Resolver cada subproblema por separado, mediante recursión.
3. Combinar el resultado de los subproblemas.

Question 3

¿Qué es la Relación de Recurrencia?

Answer 3

Es una ecuación que define una secuencia recursiva, donde cada término de la secuencia es definido como una función de términos anteriores.

T_n = F ( T_{n-1}, T_{n-2}, ... )

Existen uno o varios términos base/iniciales desde los cuales se calculan los siguientes.

Question 4

Ejemplo de Relación de Recurrencia: Mergesort: Explique los elementos de la ecuación, y defina la forma final de la misma.

Answer 4

• Sea T(n) el peor caso de tiempo de ejecución para la resolución del problema de n elementos.
• Sea DIV el proceso de dividir el problema en 2 subproblemas (O(1) <= c; c > 0).
• Sea UNI el proceso de unir el resultdo de los 2 subproblemas ( O(n) <= cn ; c > 0).

Entonces:

T(n) <= 2 * T(n/2) + DIV + UNI
T(2) <= c

Nos queda:

T(n) ≤ 2*T(n/2) + n  ;   n>2
T(2) ≤ d    ;   n=2

Question 5

Para el proceso de Desenrollar la Recurrencia, con el ejemplo de Mergesort:

• Explique la forma del árbol de recurrencia
• Explique las cantidades de subproblemas por Niveles

Answer 5

Al desarrollar la recurrencia, se arma un arbol.

Se puede ver que en cada nivel, el tamaño de los subproblemas se divide a la mitad, pero se multiplica por 2 la cantidad de subproblemas.

└── n
    └── n/2
    │   ├── n/4
    │   └── n/4
    └── n/2
        ├── n/4
        └── n/4

Question 6

Para el proceso de Desenrollar la Recurrencia, con el ejemplo de Mergesort:

• Explique el cálculo del tiempo de resolución para cada nivel
• Explique la complejidad temporal general

Answer 6

Sean:

• s el tamaño de los subproblemas: n/2^i
• m la cantidad de subproblemas: 2^i

Se puede acotar el tiempo de que se tarda en resolver el nivel i por:

T = c x ( s x m )

   = c x ( n/(2^i) x 2^i )

   = cn

Cada nivel requiere un tiempo de cn.

Hay logn niveles, ya que se necesita dividir el problema una cantidad log2 n de veces para reducirlo de n a 2. Por lo tanto, el tiempo total requerido es cn logn, por lo que la complejidad temporal general es:

O(n logn)

Question 7

Teorema Maestro: explique

Answer 7

Sean:

• a >= 1, b >= 1, constantes.
• f(b) una función
• T(n) = a T(n/b) + f(n) una recurrencia con T(0) = cte, donde a es la cantidad de llamadas recursivas y b las partes en las que se divide el problema.

Entonces:

1. Primer caso
   - Si f(n) = O ( n^( (log_b a) - e ) ) ; e >0
   - Entonces T(n) = Θ ( n^(log_b a))
2. Segundo caso
   - Si f(n) = Θ ( n^(log_b a))
   - Entonces T(n) = Θ ( n^(log_b a) * logn)
3. Tercer caso
   - Si f(n) = Ω ( n^((log_b a) + e))
   - Entonces T(n) = Θ ( f(n) )
   - Y además, a . f(n/b) <= c . f(n); c < 1, n >>

Question 8

Resuelva

T(n) = 9T(n/3) + n

Answer 8

T(n) = Θ(n^2)

Question 9

Resuelva

T(2n/3) + 1

Answer 9

f(n) = Θ(log_b a)
T(n) = O(logn)

Question 10

Resuelva

T(n) = 3 T(n/4) + n logn

Answer 10

T(n) = Θ ( f(n) ) = Θ (n logn)

Question 11

Resuelva

T(n) = 2 T(n/2) + n logn

Answer 11

No se puede calcular