17/09/2019, 04:05:58 pm *
Bienvenido(a), Visitante. Por favor, ingresa o regístrate.
¿Perdiste tu email de activación?

Ingresar con nombre de usuario, contraseña y duración de la sesión
Noticias: Puedes practicar LATEX con el cómodo editor de Latex online
 
 
Páginas: [1]   Ir Abajo
  Imprimir  
Autor Tema: Complejidad recursiva  (Leído 1282 veces)
0 Usuarios y 1 Visitante están viendo este tema.
niniodinho
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Argentina Argentina

Mensajes: 188


Ver Perfil
« : 20/06/2009, 02:06:55 pm »

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.
En línea
Páginas: [1]   Ir Arriba
  Imprimir  
 
Ir a:  

Impulsado por MySQL Impulsado por PHP Powered by SMF 1.1.4 | SMF © 2006, Simple Machines LLC XHTML 1.0 válido! CSS válido!