Questão 2974791 de Tecnologia da Informação - IFSP 2026

Questão

ID 2974791

Disciplina: Tecnologia da Informação

Assuntos: Complexidade de Algoritmos (Big-O, P x NP)

Ano: 2026 Banca: IFSP - Instituto Federal de Educação, Ciência e Tecnologia de São Paulo Órgão: Instituto Federal de Educação, Ciência e Tecnologia de São Paulo

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 contendo os seguintes dados (sensor_id, timestamp, valor) e uma lista de sensores, temos a seguinte implementação para essa tarefa:

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.

Alternativa 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.
Alternativa 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.
Alternativa 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.
Alternativa D:
Complexidade: 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.

Estatísticas Cadernos

Questão 2974791

Continue estudando na plataforma