2

Tengo un algoritmo que se puede resumir en el siguiente seudocódigo:

algoritmo()
     if (casobase)
           O(1)
    else
           for i=0 to n
                   T(n-1)
           endfor

           O(n)
    endif

El caso base de la recursión toma un tiempo de ejecución constante pero en el caso general debe ejecutar n llamados recursivos, reduciendo en 1 el tamaño de la entrada. Entonces el tiempo de ejecución para el caso general corresponderían a T(n)=n*T(n-1)+O(n), pero utilizando teorema maestro no puedo conseguir el valor del orden de complejidad O(). ¿Cómo se calcula en estos casos?

1 respuesta 1

1

El orden de complejidad corresponde a O(n!) debido a que se tiene lo siguiente para los distintos valores de n

T(1)=1*T(0)+O(n)
T(2)=2*T(1)=1*T(0)+O(n)
T(n-1)=(n-1)*T(n-2)+O(n)=(n-1)(n-2)*T(n-3)+O(n)
T(n)=n*T(n-1)+O(n)=n*(n-1)*T(n-2)+O(n)=n*(n-1)*(n-2)*T(n-3)+O(n)=~n!

Tu Respuesta

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge you have read our privacy policy.

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.