Hoja de Problemas de Programacion II - Solucion del problema 7

Problema 7

7. Calcular el orden de complejidad de las siguientes funciones recursivas (contar sólo las operaciones producto)

  function f1(n: integer) : integer;
  begin
    if n < 1 then f1 := 1 else f1 := f1(n-3)*f1(n-3)
  end;

Si denominamos T(n) al número de operaciones producto que se realizan en una llamada a la función f₁(n), podemos ver que en el caso base (n = 0) no se realiza ninguna y en cualquier otro caso se realiza una (marcada en rojo) mas las que hagan las dos llamadas recursivas f₁(n-3), Por lo tanto, la relación de recurrencia será

T(0) = 0, T(n) = 2·T(n-3)+1

Podemos ver que se ajusta al esquema T(n) = a·T(n-b)+c·n^k, donde a = 2, b = 3, c = 1, k = 0. Para este esquema sabemos que:

T(n) Î Q(n^k+1) si a = 1, T(n) Î Q(a^n/b) si a > 1.

Por lo tanto el orden de la función f₁ será Q(2^n/3).

  function f3(n: integer) : integer;
  var i,x : integer;
  begin
    if n < 1 then f3 := 1 else
    begin
      x := 1;
      for i := 1 to n do x := x*n;
      f3 := x*f3(n-1)
    end
  end

En el caso base (n = 0) no se realiza ningún producto y en cualquier otro caso se realizan n+1 productos mas los que hagan la llamada recursiva f₃(n-1). Por lo tanto, la relación de recurrencia será

T(0) = 0, T(n) = T(n-1)+n+1

Se ajusta al esquema anterior, con a = 1, b = 1, c = 1, k = 1, por lo tanto el orden de la función f₃ será Q(n²).

  function f2(n: integer) : integer;
  begin
    if n < 1 then f2 := 1 else
      f2 := f2(n div 2)*f2(n div 2)*f2(n div 2)
  end;

En el caso base (n = 0) no se realiza ningún producto y en cualquier otro caso se realizan 2 productos mas los que hagan las tres llamadas recursivas a f₂(n/2). Por lo tanto, la relación de recurrencia será

T(0) = 0, T(n) = 3·T(n/2)+2

La relación se ajusta al esquema T(n) = a·T(n/b)+c·n^k, donde a = 3, b = 2, c = 2, k = 0. Para este esquema sabemos que:

T(n) Î Q(n^k) si a < b^k

T(n) Î Q(n^k·lg n) si a = b^k

T(n) Î Q(n^log_ba) si a > b^k

Por lo tanto el orden de la función f₂ será Q(n^log₂3) = Q(n^1.585).

  function f4(n: integer) : integer;
  var i,x : integer;
  begin
    if n < 1 then f4 := 1 else
    begin
      x := 1;
      for i := 1 to n*n do x := x*2;
      f4 := x*f4(n div 2)
    end
  end

En el caso base (n = 0) no se realiza ningún producto y en cualquier otro caso se realizan n²+2 productos mas los que hagan la llamada recursiva f₄(n/2). Por lo tanto, la relación de recurrencia será

T(0) = 0, T(n) = T(n/2)+n²+2

Se ajusta al esquema anterior, con a = 1, b = 2, c = 1, k = 2, por lo tanto el orden de la función f₄ será Q(n²).

Regresar a la página de enunciados.