Questão de Algoritmos e Estrutura de Dados — Algoritmos — CONSULPAM 2025
Algoritmos e Estrutura de Dados›Algoritmos
Código
qg433561
Banca
CONSULPAM
Órgão
CONAB
Ano
2025
Nível
Superior
Cargo
Analista - Tecnologia da Informação (Desenvolvimento)
Considere o seguinte trecho de código em Python construído por um desenvolvedor:def busca(lista, alvo):for i in range(len(lista)):if lista[i] == alvo:return ireturn -1Diante do exposto, assinale a alternativa que apresenta a Complexidade do Algoritmo no melhor e no pior caso, respectivamente.
AMelhor caso: Ω(n) | Pior caso: Ω(1).
BMelhor caso: O(1) | Pior caso: O(n).
CMelhor caso: O(1) | Pior caso: O(log n).
DMelhor caso: Θ(log n) | Pior caso: Θ(n).
Revelar gabarito e comentário▾
GabaritoB — Melhor caso: O(1) | Pior caso: O(n).
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 de Algoritmos - Busca Linear
Gabarito: letra B. No melhor caso, o elemento procurado está na primeira posição, executando apenas uma iteração → O(1). No pior caso, o elemento não está na lista (ou está na última posição) e todas as n posições são percorridas → O(n). A alternativa B representa corretamente essas complexidades.
A banca testa o conhecimento de análise assintótica de algoritmos simples. O trecho de código é uma busca sequencial (ou linear) padrão.
Busca linear: Melhor caso (Alvo na 1ª posição, O(1)); Pior caso (Alvo ausente ou na última posição, O(n)); Notações (O (Big-O): limite superior, Ω (Omega): limite inferior, Θ (Theta): limite justo)
Alternativa A — ❌ Incorreta
Inverte as notações: usa Ω no melhor caso (deveria ser O(1)) e Ω no pior caso (deveria ser O(n)). Além disso, o valor Ω(1) para pior caso está errado, pois a complexidade mínima no pior caso é Ω(n).
Alternativa B — ✅ Correta ⟵ GABARITO
Melhor caso: O(1) — o primeiro elemento é o alvo. Pior caso: O(n) — percorre toda a lista. Notação Big-O correta para limitante superior.
Alternativa C — ❌ Incorreta
Afirma que o pior caso é O(log n), o que corresponderia a uma busca binária, mas o algoritmo é sequencial e não requer lista ordenada; a complexidade é O(n), não logarítmica.
Alternativa D — ❌ Incorreta
Usa Θ (theta) que indica limite justo, mas não é o mais adequado aqui: no melhor caso o algoritmo executa em tempo constante, mas pode variar (se o alvo não estiver na primeira posição, não é constante). Θ(1) no melhor caso só seria correto se o algoritmo sempre executasse exatamente 1 passo, o que não ocorre (pode ser 2, 3...). Além disso, o pior caso Θ(n) está correto, mas o melhor caso não.
NÃO CAIA NESSA!
A banca troca a notação Ω (limite inferior) por O (limite superior) e inverte os casos. Lembre-se: O = sempre pode ser pior; Ω = sempre pode ser melhor. No melhor caso da busca linear, o tempo é O(1) (não piora), mas no pior caso é O(n).