Questão 22 · Exame POSCOMP — Mestrado/Doutorado 2025 (FUNDATEC)

Question

Considere a seguinte função recursiva calcula_algo(n): def calcula_algo(n):

if n <= 1:

return 1 else:

return calcula_algo(n - 1) + calcula_algo(n - 2) Sobre a complexidade de tempo T(N) e complexidade de espaço S(N) dessa implementação recursiva, é correto afirmar que:

Accepted Answer

B) T(N)=O(2N) e S(N)=O(N), devido à exponencial duplicação de chamadas e à profundidade da pilha de chamadas.

Answer

A) T(N)=O(N) e S(N)=O(logN), devido à otimização de compilação.

Answer

C) T(N)=O(N2) e S(N)=O(N), porque cada chamada recursiva adiciona uma entrada à pilha.

Answer

D) T(N)=O(NlogN) e S(N)=O(1), pois a maioria das chamadas são memorizadas implicitamente.

Answer

E) T(N)=O(logN) e S(N)=O(N), assumindo que o sistema operacional gerencia a pilha de forma otimizada.

FUNDATEC, Exame POSCOMP

Questões parecidas