Autor Tema: Complejidad recursiva

0 Usuarios y 1 Visitante están viendo este tema.

20 Junio, 2009, 07:06 pm
Leído 1339 veces

niniodinho

  • Novato
  • Mensajes: 188
  • Karma: +0/-0
  • Sexo: Masculino
Hola. Tengo dos algoritmos de los cuales debo calcular su complejidad temporal. En el primer caso, el código es el siguiente:
int g(int z){
     //pre:z<=k
     if (z==k)
              return(d);
     else
              return(z*g(z+1));}

Lo que hize fue tomar el caso base como:
\( C_0 \) z=k
Y luego la recursión como:
\( C_1 + T(n+1) \)

Partiendo de esta base, obtuve que el i-ésimo caso era \( C_1i+T(n+i) \)
donde reemplazamos \( i=k-n \)
Finalmente, me queda lo siguiente:
\( T(n,k)=C_3+max(C_0,C_1(k-n)+T(k) \)
¿Está bien tomar la función como perteneciente a O(k), ya que es la de mayor peso?

Por otra parte, tengo un algortimo similar:
 int g(int x){
       //pre: x>=0
       if x==0
              return(1);
       else
              return(f(g(x-1)*3);} \( f\in{O(k)} \)

Aquí no sé como calcular el tiempo de la recursión. Supuse que debo sumar el tiempo de la función f, más el tiempo de la recursión, más una constante que sería la multiplicación.
Muchas gracias por su tiempo.