Questão de Algoritmos e Estrutura de Dados — Algoritmos — CESPE / CEBRASPE 2024
Algoritmos e Estrutura de Dados›Algoritmos
Código
ce191757
Banca
CESPE / CEBRASPE
Órgão
INPI
Ano
2024
Nível
Superior
Acerca de estrutura de dados e algoritmos, julgue o item a seguir.O seguinte pseudocódigo possui complexidade de tempo de pior caso O(2") para a verificação da existência de um elemento na lista.função BuscaRecursiva(lista, tamanho,elemento)se tamanho < 1 entãoretorna FALSOse lista[tamanho] == elemento entãoretorna VERDADEIROsenãoBuscaRecursiva(lista, tamanho-1, elemento)fim função
CCerto
EErrado
Revelar gabarito e comentário▾
GabaritoC — Certo
Comentário gerado por IA. É um apoio ao estudo, ancorado em fontes, mas pode conter imprecisões — confira sempre na fonte oficial (lei, súmula, edital e gabarito da banca). Encontrou um erro? Use “Reportar”.
Complexidade do algoritmo de busca recursiva
❌ ERRADO. O pseudocódigo apresentado realiza uma busca linear recursiva, percorrendo a lista do último ao primeiro elemento. No pior caso (elemento ausente), são feitas n+1 chamadas recursivas, cada uma com operações O(1). A complexidade de tempo é O(n), e não O(2ⁿ). A afirmação de que a complexidade é O(2ⁿ) está incorreta.
A função BuscaRecursiva faz uma única chamada recursiva por execução (exceto no caso base), reduzindo o tamanho em 1 a cada passo. Isso caracteriza uma recursão linear, cujo tempo de execução é proporcional ao tamanho da entrada. Não há ramificação exponencial. Portanto, o item está errado.
Característica
Descrição
Algoritmo
Busca linear recursiva
Estrutura
Percorre a lista do último ao primeiro elemento
Pior caso
Elemento ausente
Número de chamadas recursivas
n+1
Operação por chamada
O(1)
Complexidade real
O(n)
Complexidade afirmada no item
O(2ⁿ)
Correção do item
Errado
Complexidade da busca recursiva: Pior caso (elemento ausente) (n+1 chamadas recursivas, Cada chamada: O(1)); Complexidade real (O(n) — linear); Complexidade afirmada (O(2ⁿ) — exponencial)