Complexidade de tempo de um algoritmo recursivo

Como posso calcular a complexidade temporal de um 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; } } 

Analisar funções recursivas (ou até mesmo avaliá-las) é uma tarefa não trivial. Uma (na minha opinião) boa introdução pode ser encontrada em Don Knuths Concrete Mathematics .

No entanto, vamos analisar esses exemplos agora:

Nós definimos uma function que nos dá o tempo necessário para uma function. Digamos que t(n) denota o tempo necessário por pow(x,n) , isto é, uma function de n .

Então podemos concluir, que t(0)=c , porque se chamarmos pow(x,0) , temos que verificar se ( n==0 ), e depois retornar 1, o que pode ser feito em tempo constante (daí a constante c ).

Agora nós consideramos o outro caso: n>0 . Aqui nós obtemos t(n) = d + t(n-1) . Isso porque temos que verificar novamente n==1 , computar pow(x, n-1 , portanto ( t(n-1) ) e multiplicar o resultado por x verificação e a multiplicação podem ser feitas em tempo constante ( d constante ), o cálculo recursivo de pow precisa de t(n-1) .

Agora podemos “expandir” o termo 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 

Então, quanto tempo leva até chegarmos ao t(1) ? Como começamos em t(n) e subtraímos 1 em cada passo, são necessários n-1 passos para alcançar t(n-(n-1)) = t(1) . Isso, por outro lado, significa que obtemos n-1 vezes a constante d e t(1) é avaliado como c .

Então nós obtemos:

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

Então, obtemos que t(n)=(n-1) * d + c que é o elemento de O (n).

pow2 pode ser feito usando o teorema de Masters . Já que podemos supor que as funções de tempo para algoritmos estão aumentando monotonicamente. Então agora temos o tempo t(n) necessário para o cálculo de pow2(x,n) :

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

por n>0 nós recebemos

  / 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) 

O acima pode ser "simplificado" para:

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

Assim, obtemos t(n) <= t(n/2) + d , que pode ser resolvido usando o teorema dos mestres para t(n) = O(log n) (veja a seção Aplicação aos Algoritmos Populares no link wikipedia, exemplo "Pesquisa Binária").

Vamos começar com o pow1, porque é o mais simples.

Você tem uma function onde uma única execução é feita em O (1). (Verificação de condição, retorno e multiplicação são constantes.)

O que você deixou é a sua recursion. O que você precisa fazer é analisar com que frequência a function acabaria chamando a si mesma. Em pow1, isso acontecerá N vezes. N * O (1) = O (N).

Para pow2, é o mesmo princípio – uma única execução da function é executada em O (1). No entanto, desta vez você está diminuindo pela metade o tempo todo. Isso significa que ele executará log2 (N) vezes – efetivamente uma vez por bit. log2 (N) * O (1) = O (log (N)).

Algo que pode ajudá-lo é explorar o fato de que a recursividade sempre pode ser expressa como iteração (nem sempre de forma muito simples, mas é possível. Podemos expressar o poder como

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

Agora você tem um algoritmo iterativo e pode achar mais fácil analisá-lo dessa maneira.

Pode ser um pouco complexo, mas acho que a maneira usual é usar o teorema do Mestre .

Complexidade de ambas as funções ignorando a recursion é O (1)

Para o primeiro algoritmo pow1 (x, n) a complexidade é O (n) porque a profundidade da recursividade se correlaciona com n linearmente.

Para a segunda complexidade é O (log n). Aqui recapitulamos aproximadamente log2 (n) vezes. Jogando fora 2 recebemos log n.

Então eu estou supondo que você está aumentando x para o poder n. pow1 pega O (n).

Você nunca muda o valor de x, mas você toma 1 de n a cada vez até chegar a 1 (e então simplesmente retorna) Isto significa que você fará uma chamada recursiva n vezes.