Page 214 - INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS

INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS

3. El método maestro da solución a recurrencias de la forma

4. donde y f (n) es una función dada.

Método de selección y Generalización

Es el método más simple y sencillo (Ramírez Benavides, 30):

• Se va evaluando la recurrencia para ciertos valores

• Se deduce, a partir del comportamiento mostrado, una ecuación que represente el
comportamiento de la recurrencia.

• Se generaliza la solución, encontrando un patrón

• Se demuestra que la ecuación efectivamente resuelve a la recurrencia.

Considere la siguiente relación de recurrencia

• Construir una tabla con los valores que toma RR para diferentes soluciones de n

• TIP: Notar que la RR solo queda definida cuando n es potencia de dos

208