Introducción a los Algoritmos – Parte IV – Análisis de Recurrencias

Como ya hemos indicado, el análisis del tiempo de ejecución de un programa recursivo vendrá en función del tiempo requerido por la(s) llamada(s) recursiva(s) que aparezcan en él. De la misma manera que la verificación de programas recursivos requiere de razonar por inducción, para tratar apropiadamente estas llamadas, el cálculo de su eficiencia requiere un concepto análogo: el de ecuación de recurrencia.

Demostraciones por inducción y ecuaciones de recurrencia son por tanto los conceptos básicos para tratar programas recursivos.
Supongamos que se está analizando el coste de un algoritmo recursivo, intentando calcular una función que indique el uso de recursos, por ejemplo el tiempo, en términos del tamaño de los datos; denominémosla T(n) para datos de tamaño n. Nos encontramos con que este coste se define a su vez en función del coste de las llamadas recursivas, es decir, de T(m) para otros
tamaños m (usualmente menores que n). Esta manera de expresar el coste en función de sí misma es lo que denominaremos una ecuación recurrente y su resolución, es decir, la obtención para T de una fórmula cerrada (independiente de T) puede ser dificultosa.

Las ecuaciones de recurrencia son utilizadas para determinar cotas asintóticas en algoritmos que presentan recursividad.

Veremos dos técnicas básicas y una auxiliar que se aplican a diferentes clases de recurrencias:

  • Método del teorema maestro
  • Método de la ecuación característica
  • Cambio de variable

No analizaremos su demostración formal, sólo consideraremos su aplicación para las recurrencias generadas a partir del análisis de
algoritmos.

Método del Teorema Maestro

Se aplica en casos como:

Teorema: Sean a = 1, b > 1 constantes, f(n) una función y T(n) una recurrencia definida sobre los enteros no negativos de la forma T(n) = aT(n/b) + f(n), donde n/b puede interpretarse como [n/b] o [n/b].

Entonces valen:

 

Método de la Ecuación Característica

Se aplica a ciertas recurrencias lineales con coeficientes constantes como:

En general, para recurrencias de la forma:

donde ai, 1 <= i >=, b son constantes y p(n) es un polinomio en n de grado s.

Ejemplos:

En general, para:

 

Cambio de Variable

Dada la siguiente ecuación de recurrencia:

No se puede aplicar el teorema maestro ni la ecuación característica.

Se define una nueva recurrencia S(i) = T(2i), con el objetivo de llevarla a una forma en la que se pueda resolver siguiendo algún método anterior. Entonces el caso general queda:

Con b=2 y p(i) = i de grado 1.

La ecuación característica de esta recurrencia es:

(x – 2)(x – 2)i+1 = 0,

con raíz 2 de grado 3.

La solución es entonces S(i) = c112i + c12 i2i + c13i22i, con lo que volviendo a la variable original queda:

Se pueden obtener los valores de las constantes sustituyendo esta solución en la recurrencia original:

de donde c12 = c13 y 2c12 = 1.

Por tanto T(n) ∈ Θ(nlog2 n | n es potencia de 2).

Si se puede probar que T(n) es eventualmente no decreciente, por la regla de las funciones de crecimiento suave se puede extender el resultado a todos los n (dado que nlog2n es de crecimiento suave).

En este caso T(n) ∈ Θ(nlog2 n).

 

Ejemplos de cálculo del tiempo de ejecución de un programa

Veamos el análisis de un simple enunciado de asignación a una variable entera:

a = b;

Como el enunciado de asignación toma tiempo constante, está en Θ(1).

Consideremos un simple ciclo “for”:

sum=0;
for (i=1; i<=n; i++)
sum += n;

La primera línea es Θ(1). El ciclo “for” es repetido n veces. La tercera línea toma un tiempo constante también, el costo total por ejecutar las dos líneas que forman el ciclo “for” es Θ(n). El costo por el entero fragmento de código es también Θ(n).

Analicemos un fragmento de código con varios ciclos “for”, algunos de los cuales están anidados.

sum=0;
  for (j=1; j<=n; j++)
      for (i=1; i<=j; i++)
           sum++;
  for (k=1; k<=n; k++)
           A[k]= k-1;

Este código tiene tres partes: una asignación, y dos ciclos. La asignación toma tiempo constante, llamémosla c1. El segundo ciclo es
similar al ejemplo anterior y toma c2n= Θ(n). Analicemos ahora el primer ciclo, que es un doble ciclo anidado. En este caso trabajemos de adentro hacia fuera. La expresión sum++ requiere tiempo constante, llamemosle c3.

Como el ciclo interno es ejecutado j veces, tiene un costo de c3j. El ciclo exterior es ejecutado n veces, pero cada vez el costo del ciclo interior es iferente.

El costo total del ciclo es c3 veces la suma de los números 1 a n, es decir  Σ n i=1 j = n(n+1)/2, que es Θ(n2). Por tanto, Θ(c1 +c2n+c3n2) es simplemente Θ(n2 ).

Comparemos el análisis asintótico de los siguientes fragmentos de código:

sum1=0;
  for(i=1; i<=n; i++)
    for(j=1; j<=n; j++)
       sum1 ++;

sum2=0;
for(i=1; i<=n; i++)
  for(j=1; j<=i; j++)
    sum2++;

El primer fragmento de ejecuta el enunciado sum1++, precisamente n2 veces. Por otra parte, el segundo fragmento de código tiene un costo aproximado de ½ n2 . Así ambos códigos tienen un costo de Θ(n2).

Ejemplo, no todos los ciclos anidados son Θ(n2):

sum1=0;
for(k=1; k<=n; k*=2)
  for(j=1; j<=n; j++)
    sum1++;

El costo es Θ(n log n).


En la próxima comenzamos con las estrategias de diseño.

 

 

Dejá un comentario