Questão 668901 · 27ª da prova
IF-SP 2026 – IF-SP – Analista de Tecnologia da Informação: Algoritmos
- Banca
- IF-SP
- Órgão
- IF-SP
- Ano
- 2026
- Cargo
- Analista de Tecnologia da Informação
- Matéria
- Algoritmos e Estrutura de Dados
- Assunto
- Algoritmos
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 agregado
Para 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 = 0
for evento in eventos: if evento[0] == sensor_id and evento[2] > limite:
total += 1 relatorio.append((sensor_id, total))
return relatorio
Sabendo 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.
- A
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.
- B
Complexidade: 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.
- C
Complexidade: 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.