¿Cómo puedo calcular la complejidad temporal de un algoritmo recursivo?Complejidad del 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;
}
}
Analizando las funciones recursivas (o incluso evaluación de las mismas) es una tarea trivial. a (en mi opinión) buena introducción se puede encontrar en Don Knuths Concrete Mathematics.
Sin embargo, analicemos ahora estos ejemplos:
Definimos una función que nos da el tiempo que necesita una función. Digamos que t(n) denota el tiempo necesario por pow(x,n), es decir, una función de n.
Entonces podemos concluir, que t(0)=c, porque si llamamos pow(x,0), tenemos que comprobar si (n==0), y luego regresar 1, que se puede realizar en un tiempo constante (de ahí la constante c).
Ahora consideramos el otro caso: n>0. Aquí obtenemos t(n) = d + t(n-1). Esto se debe a que tenemos que verificar nuevamente n==1, calcular , por lo tanto (t(n-1)), y multiplicar el resultado por x.La verificación y la multiplicación se pueden realizar en tiempo constante (constante d), el cálculo recursivo de pow necesita .
Ahora podemos "ampliar" 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
Así que, ¿cuánto tiempo se tarda hasta llegar a t(1)? Como comenzamos en t(n) y restamos 1 en cada paso, lleva n-1 pasos para llegar al t(n-(n-1)) = t(1). Eso, por otro lado, significa que obtenemos n-1 veces la constante d, y t(1) se evalúa a c.
Así obtenemos:
t(n) =
...
d + d + d + ... + c =
(n-1) * d + c
por lo que tenemos que t(n)=(n-1) * d + c elemento que es de O (n).
pow2 se puede hacer usando Masters theorem. Como podemos suponer que las funciones de tiempo para los algoritmos son monótonamente crecientes. Así que ahora tenemos el tiempo t(n) necesaria 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" a:
t(n) = floor(t(n/2)) + d <= t(n/2) + d (since t is monotonically increasing)
Por lo tanto, obtenga t(n) <= t(n/2) + d, que se puede resolver usando el teorema de maestros a t(n) = O(log n) (consulte la sección Aplicación a Popul ar Algoritmos en el enlace de wikipedia, ejemplo "Búsqueda binaria").
Puede ser un poco complejo, pero creo que la forma habitual es utilizar Master's theorem.
Complejidad de ambas funciones haciendo caso omiso de recursión es O (1)
Por primera pow1 algoritmo (x, n) la complejidad es O (n), ya que la profundidad de recursión se correlaciona con n linealmente.
Para la segunda complejidad es O (log n). Aquí recurrimos aproximadamente log2 (n) veces. Al tirar 2 obtenemos log n.
Así que supongo que estás elevando x a la potencia n. pow1 toma O (n).
Nunca cambia el valor de x pero toma 1 de n cada vez hasta que llegue a 1 (y luego simplemente regrese) Esto significa que hará una llamada recursiva n veces.
Comencemos con pow1, porque es el más simple.
Tiene una función en la que una sola ejecución se realiza en O (1). (La verificación, el retorno y la multiplicación de la condición son constantes).
Lo que queda es la 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 ayudarle es explotar el hecho de que la recursividad siempre se puede expresar como iteración (no siempre de manera muy sencilla, pero es posible. Podemos expresar pow1 como
result = 1;
while(n != 0)
{
result = result*n;
n = n - 1;
}
Ahora usted tiene un algoritmo iterativo en su lugar, y puede que le resulte más fácil de analizar esa manera.
Este enlace proporciona la respuesta exacta a su problema. Aquí está la fuente (http://www.cs.ucf.edu/~dmarino/ucf/cop3502/lec_biswas/recursion12.pdf)
* La complejidad de ambas funciones es O (1) * - ¿Qué? – kennytm
O (1) ignora la llamada recursiva pero podría expresarse de manera diferente. El punto es que la complejidad total depende únicamente de la profundidad de recursión. – fgb