recursivos - determinar la complejidad de un algoritmo online

Complejidad temporal de un algoritmo recursivo.

Question

¿Cómo puedo calcular la complejidad de tiempo 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;
    }
}

Answer 1

Analizar funciones recursivas (o incluso evaluarlas) no es una tarea trivial. Una (en mi opinión) buena introducción se puede encontrar en Don Knuths Concrete Mathematics .

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 que necesita pow(x,n) , es decir, una función de n .

Luego podemos concluir que t(0)=c , porque si llamamos pow(x,0) , tenemos que verificar si ( n==0 ), y luego devolver 1, que se puede hacer en tiempo constante (por lo tanto la constante c ).

Ahora consideramos el otro caso: n>0 . Aquí obtenemos t(n) = d + t(n-1) . Esto se debe a que nuevamente tenemos que verificar n==1 , calcular el poder pow(x, n-1 , por lo tanto ( 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 las necesidades de pow 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 se tarda en llegar a t(1) ? Como comenzamos en t(n) y restamos 1 en cada paso, se necesitan n-1 pasos para alcanzar t(n-(n-1)) = t(1) . Eso, por otra parte, significa que obtenemos n-1 veces la constante d , y t(1) se evalúa para c .

Así obtenemos:

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

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

pow2 se puede hacer usando el teorema de Masters . Ya que podemos asumir que las funciones de tiempo para los algoritmos están aumentando 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))

para 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 puede ser "simplificado" para:

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

Entonces obtenemos t(n) <= t(n/2) + d , que puede resolverse usando el teorema de los maestros para t(n) = O(log n) (ver sección Aplicación a los algoritmos populares en el enlace de wikipedia, ejemplo "Búsqueda binaria").

Answer 2

Así que supongo que estás elevando x al poder n. pow1 toma O (n).

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

Answer 3

La complejidad de ambas funciones ignorando la recursión es O (1)

Para el primer algoritmo, pow1 (x, n) la complejidad es O (n) porque la profundidad de la recursión se correlaciona con n linealmente.

Para la segunda complejidad es O (log n). Aquí repuntamos aproximadamente log2 (n) veces. Desechando 2 obtenemos log n.

Answer 4

Puede ser un poco complejo, pero creo que la forma habitual es usar el teorema de Master .

Answer 5

Vamos a empezar con pow1, porque ese es el más simple.

Tiene una función en la que se realiza una única ejecución en O (1). (La verificación de la condición, el retorno y la multiplicación son tiempo constante).

Lo que te queda es entonces tu recursión. Lo que hay que hacer es analizar la frecuencia con la que 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 única 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 puede expresarse como iteración (no siempre 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 y puede que le resulte más fácil analizarlo de esa manera.