Algoritmos e Estrutura de Dados · IF-SP · 2026 | Questão sqc-qg710306

Algoritmos e Estrutura de DadosAlgoritmos

Código: qg710306
Banca: IF-SP
Órgão: IF-SP
Ano: 2026
Nível: Superior

Cargo: Analista de Tecnologia da Informação

Uma empresa coleta eventos de sensores IoT. Cada evento contém um identificador, o horário e um valor agregado ao evento:• Identificador do sensor• Data e hora do evento• Valor agregadoPara monitorar algumas atividades, é gerado um relatório que indique a quantidade de eventos para os quais o valor agregado está acima de um limite.Considerando uma lista de eventos, onde cada evento é representado por uma tupla con tendo os seguintes dados (sensor_id, timestamp, valor) e uma lista de sensores, temos a seguinte implementação para essa tarefa:def gerar_relatorio(eventos, sensores, limite): relatorio = []for sensor_id in sensores: total = 0for evento in eventos: if evento[0] == sensor_id and evento[2] > limite:total += 1 relatorio.append((sensor_id, total))return relatorioSabendo que:• A lista de eventos possui N registros (na ordem de milhões de eventos);• A lista de sensores contém S sensores (na odem de centenas de sensores);• Cada evento pertence a um sensor específico. Analise a complexidade assintótica do algoritmo e selecione a alternativa correta.

AComplexidade: O(S × N)Cada sensor percorre todos os eventos, levando a um custo de N comparações por sensor. Para grandes volumes de dados, tem escalabilidade ruim. Pode ser otimizado agrupando eventos por sensor antes de contar.
BComplexidade: O(N + S)Cada evento é processado apenas uma vez, usando uma lista de contagem. É uma solução eficiente e escalável para grandes volumes de dados.
CComplexidade: O(N²)Todos os eventos são comparados entre si para cada sensor. Como o número de eventos sempre é maior que o de sensores, o custo é quadrático pelos eventos de entrada. O algoritmo é ineficiente para grandes volumes de dados. Uma abordagem melhor é agrupar eventos por sensor e depois contar.
DComplexidade: O(S² + N) Para cada sensor, é necessário combinar pares de sensores e eventos antes de contar, levando a um custo quadrático sobre sensores.O algoritmo é ineficiente para grandes volumes de dados. Devido a ser um problema altamente complexo, não existe uma solução melhor que a implementada.

Revelar gabarito e comentário

GabaritoA — Complexidade: O(S × N) Cada sensor percorre todos os eventos, levando a um custo de N comparações por sensor. Para grandes volumes de dados, tem escalabilidade ruim. Pode ser otimizado agrupando eventos por sensor antes de contar.

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 - Laços Aninhados

Gabarito: letra A. A complexidade assintótica do algoritmo apresentado é O(S × N), pois ele possui dois laços aninhados: o externo percorre a lista de sensores (S) e, para cada sensor, o interno percorre toda a lista de eventos (N), realizando S × N comparações no pior caso.

O código fornecido:

def gerar_relatorio(eventos, sensores, limite):
    relatorio = []
    for sensor_id in sensores:
        total = 0
        for evento in eventos:
            if evento[0] == sensor_id and evento[2] > limite:
                total += 1
        relatorio.append((sensor_id, total))
    return relatorio

O laço externo executa S iterações; o interno, N iterações para cada execução do externo. Logo, o número total de operações é proporcional a S × N, resultando na complexidade O(S × N).

Alternativa A — ✅ Correta ⟵ GABARITO

Conforme explicado, a complexidade é O(S × N). A descrição está correta: cada sensor percorre todos os eventos, resultando em N comparações por sensor, totalizando S × N.

Alternativa B — ❌ Incorreta

Afirma que a complexidade é O(N + S), linear. Isso seria verdade se o algoritmo percorresse uma única vez cada lista, mas ele percorre N eventos para cada sensor, gerando O(S × N). A solução proposta (usar uma lista de contagem) seria mais eficiente, mas não corresponde ao algoritmo implementado.

Alternativa C — ❌ Incorreta

Afirma complexidade O(N²). O número de comparações não é proporcional a N², pois o laço externo itera sobre S (centenas) e não sobre N. A complexidade é O(S × N), não quadrática em N.

Alternativa D — ❌ Incorreta

Afirma complexidade O(S² + N) e menciona combinação de pares de sensores. O algoritmo não realiza nenhuma combinação entre sensores; ele apenas compara cada evento com cada sensor individualmente, resultando em O(S × N).

NÃO CAIA NESSA!

Em análise de complexidade, observe sempre os laços aninhados. Um laço externo que itera A vezes e um interno que itera B vezes (sem dependências) resulta em O(A × B). Cuidado para não confundir com O(A + B), que ocorre quando os laços são sequenciais, não aninhados.

Gabarito: letra A

Link permanente: /questoes/qg710306