Disciplinas relacionadas con la matemática => Temas de computación => Mensaje iniciado por: niniodinho en 20 Junio, 2009, 14:06



Título: Complejidad recursiva
Publicado por: niniodinho en 20 Junio, 2009, 14:06
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:
[texx]C_0[/texx] z=k
Y luego la recursión como:
[texx]C_1 + T(n+1)[/texx]

Partiendo de esta base, obtuve que el i-ésimo caso era [texx]C_1i+T(n+i)[/texx]
donde reemplazamos [texx]i=k-n[/texx]
Finalmente, me queda lo siguiente:
[texx]T(n,k)=C_3+max(C_0,C_1(k-n)+T(k)[/texx]
¿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);} [texx]f\in{O(k)}[/texx]

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.