2

Preciso saber como cálcular a complexidade deste algoritmo usando a equação de recorrência.

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

É um algorítmo recursivo que lê dois números x e n e retorna o resultado de x^n

3
  • Trabalho de casa lol
    – Jorge B.
    Commented 8/09/2014 às 15:33
  • @JorgeB. é lista de exercicios da Faculdade, é que tenho prova hoje e preciso entender como calcular a complexidade de algorítmos recursivos usando a equação de recorrência kk Commented 8/09/2014 às 15:36
  • google.pt/…
    – Jorge B.
    Commented 8/09/2014 às 15:42

1 Resposta 1

3

e bem simples :)

quando n > 1, a função faz uma operação que tem tempo constante, a multiplicação, e faz uma chamada recursiva que tem tamanho n - 1.

logo, a recorrência fica:

T(n) = T(n-1) + 1 (ou O(1), da na mesma)
T(1) = 1

se você resolver você vai chegar em uma soma do tipo 1 + 1 + 1+ ... + 1, com n uns. isso da n. logo, a função é linear, O(n).

1
  • entendi, vou continuar estudando aqui :D valeu! Commented 8/09/2014 às 15:28

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .