Complejidad temporal de un algoritmo recursivo

¿Cómo puedo calcular la complejidad temporal de un algoritmo recursivo?

int pow1(int x,int n) {
    if(n==0){
        return 1;
    }
    else{
        return x * pow1(x, n-1);
    }
}

int pow2(int x,int n) {
    if(n==0){
        return 1;
    }
    else if(n&1){
        int p = pow2(x, (n-1)/2)
        return x * p * p;
    }
    else {
        int p = pow2(x, n/2)
        return p * p;
    }
}

Analizar funciones recursivas (o incluso evaluarlas) no es una tarea trivial. Una (en mi opinión) buena introducción se puede encontrar en Matemáticas concretas de Don Knuth.

Sin embargo, analicemos estos ejemplos ahora:

Definimos una función que nos da el tiempo que necesita una función. digamos que t(n) denota el tiempo necesario para pow(x,n)es decir, una función de n.

Entonces podemos concluir, que t(0)=cporque si llamamos pow(x,0)tenemos que comprobar si (n==0), y luego devuelva 1, lo que se puede hacer en tiempo constante (de ahí la constante c).

Ahora consideremos el otro caso: n>0. Aquí obtenemos t(n) = d + t(n-1). Eso es porque tenemos que comprobar de nuevo n==1calcular pow(x, n-1por eso (t(n-1)), y multiplicar el resultado por x. La verificación y la multiplicación se pueden hacer en tiempo constante (constante d), el cálculo recursivo de pow necesidades t(n-1).

Ahora podemos “expandir” el término t(n):

t(n) =
d + t(n-1) = 
d + (d + t(n-2)) = 
d + d + t(n-2) = 
d + d + d + t(n-3) =
... =
d + d + d + ... + t(1) =
d + d + d + ... + c

Entonces, ¿cuánto tiempo lleva hasta que lleguemos t(1)? Ya que empezamos en t(n) y restamos 1 en cada paso, se necesita n-1 pasos para llegar t(n-(n-1)) = t(1). Eso, por otro lado, significa que obtenemos n-1 veces la constante dy t(1) se evalúa a c.

Así obtenemos:

t(n) =
...
d + d + d + ... + c =
(n-1) * d + c

Entonces conseguimos eso t(n)=(n-1) * d + c que es elemento de O(n).

pow2 se puede hacer usando teorema de maestros. Dado que podemos suponer que las funciones de tiempo para los algoritmos aumentan monótonamente. Así que ahora tenemos el tiempo t(n) necesario para el cálculo de pow2(x,n):

t(0) = c (since constant time needed for computation of pow(x,0))

por n>0 obtenemos

        / t((n-1)/2) + d if n is odd  (d is constant cost)
t(n) = <
        \ t(n/2) + d     if n is even (d is constant cost)

Lo anterior se puede “simplificar” a:

t(n) = floor(t(n/2)) + d <= t(n/2) + d (since t is monotonically increasing)

Entonces obtenemos t(n) <= t(n/2) + dque se puede resolver usando el teorema de masters para t(n) = O(log n) (consulte la sección Aplicación a algoritmos populares en el enlace de wikipedia, ejemplo “Búsqueda binaria”).

Comencemos con pow1, porque es el más simple.

Tiene una función donde se realiza una sola ejecución en O (1). (La verificación de condiciones, la devolución y la multiplicación son tiempo constante).

Lo que te queda es entonces tu recursividad. Lo que debe hacer es analizar con qué frecuencia la función terminaría llamándose a sí misma. En pow1, sucederá N veces. N*O(1)=O(N).

Para pow2, es el mismo principio: una sola ejecución de la función se ejecuta en O(1). Sin embargo, esta vez estás reduciendo a la mitad N cada vez. Eso significa que ejecutará log2(N) veces, efectivamente una vez por bit. log2(N)*O(1)=O(log(N)).

Algo que podría ayudarlo es aprovechar el hecho de que la recursión siempre se puede expresar como iteración (no siempre de manera muy simple, pero es posible. Podemos expresar pow1 como

result = 1;
while(n != 0)
{
  result = result*n;
  n = n - 1;
}

Ahora tiene un algoritmo iterativo en su lugar, y puede que le resulte más fácil analizarlo de esa manera.

Puede ser un poco complejo, pero creo que la forma habitual es usar teorema del maestro.

Así que supongo que estás elevando x a la potencia n. pow1 toma O(n).

Nunca cambias el valor de x, pero tomas 1 de n cada vez hasta que llega a 1 (y luego regresas). Esto significa que harás una llamada recursiva n veces.