Questão de Algoritmos e Estrutura de Dados — Algoritmos — CONSULPAM 2025
Algoritmos e Estrutura de Dados›Algoritmos
Código
qg433560
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 soma_parcial(lista):total = 0for i in range(len(lista)):if lista[i] % 2 == 0:total += lista[i]return totalSabendo que lista é não vazia e contém n inteiros, assinale a alternativa que apresenta a Complexidade do Algoritmo no melhor e no pior caso, respectivamente.
AMelhor caso: O(1) | Pior caso: O(n).
BMelhor caso: Ω(n) | Pior caso: Θ(n).
CMelhor caso: Ω(1) | Pior caso: O(n).
DMelhor caso: Θ(1) | Pior caso: Θ(n log n).
Revelar gabarito e comentário▾
GabaritoB — Melhor caso: Ω(n) | Pior caso: Θ(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 - Análise de Código Python
Gabarito: alternativa B. O algoritmo percorre integralmente toda a lista de tamanho n, independentemente de quantos elementos são pares. Isso significa que tanto no melhor caso (todos ímpares) quanto no pior (todos pares) a complexidade é linear: Θ(n). A alternativa B expressa corretamente isso usando Ω(n) para o melhor caso (limite inferior) e Θ(n) para o pior caso (limite justo).
Alternativa A — ❌ Incorreta
Afirma que o melhor caso é O(1). Isso seria verdade apenas se o algoritmo pudesse terminar sem percorrer toda a lista, mas o loop for i in range(len(lista)) sempre executa n iterações. O melhor caso é, na verdade, Ω(n).
Alternativa B — ✅ Correta ⟵ GABARITO
Usa a notação correta: Ω(n) para o melhor caso (limite inferior linear) e Θ(n) para o pior caso (limite justo linear). Como o número de operações é sempre proporcional a n, ambas as notações estão adequadas.
Alternativa C — ❌ Incorreta
Apresenta o melhor caso como Ω(1). O erro é semelhante ao da alternativa A: o loop não pode ser interrompido antes de percorrer todos os elementos, portanto o melhor caso é Ω(n), não Ω(1). O pior caso como O(n) está correto, mas a combinação invalida a alternativa.
Alternativa D — ❌ Incorreta
Erra duplamente: o melhor caso não é Θ(1) e o pior caso não é Θ(n log n). O algoritmo não contém nenhuma operação logarítmica (como divisão e conquista) — é apenas um loop simples, de complexidade linear Θ(n) para qualquer entrada.
NÃO CAIA NESSA!
A armadilha está em associar o melhor caso a nenhum elemento par e concluir que o algoritmo "faz menos trabalho". Na verdade, o range(len(lista)) força a iteração sobre todos os n elementos, independentemente do conteúdo da condicional if. Sempre haverá n iterações, portanto a complexidade é linear constante.