Pular para o conteúdo principal

Questão de TI - Desenvolvimento de Sistemas — Complexidade de Algoritmos — FUNDATEC 2025

TI - Desenvolvimento de SistemasComplexidade de Algoritmos
Código
qa699552
Banca
FUNDATEC
Órgão
SBC
Ano
2025
Cargo
POSCOMP ( )
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:
  1. AT(N)=O(N) e S(N)=O(logN), devido à otimização de compilação.
  2. BT(N)=O(2N) e S(N)=O(N), devido à exponencial duplicação de chamadas e à profundidade da pilha de chamadas.
  3. CT(N)=O(N2) e S(N)=O(N), porque cada chamada recursiva adiciona uma entrada à pilha.
  4. DT(N)=O(NlogN) e S(N)=O(1), pois a maioria das chamadas são memorizadas implicitamente.
  5. ET(N)=O(logN) e S(N)=O(N), assumindo que o sistema operacional gerencia a pilha de forma otimizada.
Revelar gabarito e comentário

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

Link permanente: /questoes/qa699552