LÓGICA E LINGUAGEM DE PROGRAMAÇÃO

Detetives de performance

Registro de Aula S10A3 — Semana 10 · Aula 3 – Comparando complexidade: O(n²) e O(n)
Unidade 2 – Eficiência de algoritmosBase: Capítulos 21 a 27 — laços, laços aninhados e listasTempo: 45 a 50 minEntrega: AVA (doc, pdf ou imagem)Arquivo: NOME_TURMA_S10A3
ATIVIDADE PROPOSTA

O que vocês vão resolver

Vocês são desenvolvedores júnior em uma startup. O sistema de busca do e-commerce está lento e a equipe precisa descobrir por quê. Há dois algoritmos propostos para encontrar produtos duplicados no estoque: um usa loops aninhados — O(n²), o outro usa uma estrutura auxiliar — O(n). A missão do grupo é rastrear os dois na mão, contar as comparações de cada um e entender por que um é mais eficiente. Lista de teste: [10, 20, 30, 20, 50].

OBJETIVOS

O que vocês vão aprender aqui

SOLUÇÃO DIGITAL

Ferramenta usada nesta aula

MESA
Teste de mesa (papel) + editor de pseudocódigo
Esta atividade é de rastreamento manual: o grupo percorre os dois algoritmos no papel, anotando cada comparação — o chamado teste de mesa. O editor de pseudocódigo serve para registrar os algoritmos; o relatório é preenchido nesta página e exportado em PDF pelo navegador.
ENTENDA

Dois caminhos para o mesmo resultado

Os dois algoritmos encontram o mesmo duplicado (o 20). O que muda é o <b>preço</b> que cada um cobra em número de comparações — e esse preço cresce de formas muito diferentes.

Algoritmo lento — O(n²)Para cada elemento i na lista (de 1 a 5):Para cada elemento j na lista (de i+1 a 5):Se lista[i] = lista[j]:Marcar como duplicado compara CADA elemento com TODOS os outrosUm laço dentro do outro: é o “aninhado” que faz o custo crescer ao quadrado.
Algoritmo rápido — O(n)Criar lista vazia "numerosVistos"Para cada elemento na lista:Se elemento está em numerosVistos:Marcar como duplicadoSenão:Adicionar elemento em numerosVistos percorre a lista UMA vez, lembrando do que já viuA estrutura auxiliar troca “comparar com todos” por “consultar o que já foi visto”.
5 elementos 10 × 5 O(n²) = 10 comparações · O(n)= 5 · 2× mais rápido 100 elementos 10.000 × 100 O(n²) ≈ 10.000 · O(n) ≈ 100 ·100× mais rápido 1.000.000 e aqui? vocês calculam no Passo 6 — éo ponto da atividade O mesmo problema, a mesma resposta: o que muda é quanto o computador precisa trabalhar.

Como preencher este relatório

  1. 1Leia o cenário e observe os diagramas — eles mostram o conceito que a sua resposta precisa usar.
  2. 2Preencha a identificação do grupo no Passo 0.
  3. 3Responda um passo de cada vez, na ordem. Cada passo traz uma dica de como pensar logo abaixo do enunciado.
  4. 4Confira o checklist no final — ele verifica se não ficou nada faltando.
  5. 5Clique em Gerar PDF da resposta. Na janela de impressão, escolha Destino: Salvar como PDF e salve como NOME_TURMA_S10A3.
  6. 6Envie esse PDF no AVA. O que vocês digitarem fica salvo neste computador sozinho — dá para fechar a página e voltar depois.
PASSO 0

Identificação

Estes dados montam a capa e a folha de rosto do relatório em PDF.

PROCEDIMENTOS

Rastreiem os dois algoritmos

Façam o teste de mesa no caderno primeiro, anotando cada comparação; depois transcrevam aqui.

1
Preparação: registrem a lista de teste e organizem o teste de mesa.
Como pensar: Desenhem a lista no caderno e reservem espaço para anotar todas as comparações. Cada número é o código de um produto — repare que um deles aparece duas vezes.
2
Rastreiem o algoritmo lento — O(n²), passada por passada.
Como pensar: Na passada 1, o 10 é comparado com todos os que vêm depois dele (4 comparações). Na passada 2, o 20 com os seguintes (3), e assim por diante — o número de comparações vai diminuindo.
PassadaComparações feitas nesta passadaAchou duplicado?Total acumulado
1 (elemento 10)
2 (elemento 20)
3 (elemento 30)
4 (elemento 20)
3
Fechem a conta do algoritmo O(n²).
Como pensar: Somem os totais de todas as passadas. Confiram: o resultado deve bater com 4 + 3 + 2 + 1.
4
Rastreiem o algoritmo rápido — O(n), passo por passo.
Como pensar: Aqui a lista auxiliar “numerosVistos” começa vazia e vai crescendo. Em cada passo, anotem o que havia nela ANTES de decidir.
PassoEstá em numerosVistos?Ação tomadanumerosVistos depois
1 (elemento 10)
2 (elemento 20)
3 (elemento 30)
4 (elemento 20)
5 (elemento 50)
5
Fechem a conta do algoritmo O(n).
Como pensar: Repare: o número de comparações é igual ao número de elementos da lista. É daí que vem o nome O(n).
6
Comparem o crescimento dos dois algoritmos.
Como pensar: Para o O(n²), multipliquem o número de elementos por ele mesmo. Para o O(n), é o próprio número de elementos. A última linha é a que revela o problema de verdade.
Tamanho da listaComparações — O(n²)Comparações — O(n)Quantas vezes mais rápido
5 elementos
100 elementos
1.000.000 elementos
7
Como o teste de mesa ajudou a entender o que o computador faz?
Como pensar: Primeira pergunta do roteiro. Comparem a experiência de rastrear as 10 e as 5 comparações na mão com apenas ler a definição teórica de Big-O.
8
Qual foi a sensação de ver o segundo algoritmo chegar ao mesmo resultado com metade do esforço?
Como pensar: Segunda pergunta do roteiro. Liguem isso à importância de escolher a abordagem certa antes de começar a programar.
9
E com 1.000.000 de elementos? Por que conhecer a complexidade importa num sistema real?
Como pensar: Terceira pergunta do roteiro. Usem o número que vocês calcularam na última linha da tabela do Passo 6 — ele fala por si.
CONFIRA

Checklist antes de gerar o PDF

Ao clicar em “Gerar PDF da resposta”, o navegador monta o relatório completo no padrão de roteiro de aula prática — com capa, folha de rosto, objetivos, procedimentos, as respostas do grupo e as referências. Na janela de impressão, escolha Destino: Salvar como PDF, salve como NOME_TURMA_S10A3 e envie no AVA.
AVALIAÇÃO

Como esta atividade será avaliada

CritérioPontos
Rastreamento correto do algoritmo O(n²) (10 comparações)3,0
Rastreamento correto do algoritmo O(n) (5 comparações)3,0
Tabela de crescimento coerente para 100 e 1.000.000 de elementos2,0
Qualidade das três respostas de reflexão2,0
REFERÊNCIAS

De onde veio o conteúdo desta aula

Curso Técnico em Desenvolvimento de Sistemas
Roteiro de Aula Prática
Lógica e Linguagem de Programação
Detetives de performance
São Paulo - SP
2026
Roteiro de Aula Prática
Detetives de performance
Roteiro de Aula Prática apresentado ao componente curricular Lógica e Linguagem de Programação, como requisito parcial de avaliação do 2º bimestre.
São Paulo - SP
2026

Roteiro de Aula Prática

Nome da disciplina: LÓGICA E LINGUAGEM DE PROGRAMAÇÃO
Unidade: 2 – Eficiência de algoritmos
Aula: 3 – Comparando complexidade: O(n²) e O(n)
Base teórica: Capítulos 21 a 27 — laços, laços aninhados e listas

Objetivos

  • Rastrear manualmente a execução de dois algoritmos (teste de mesa), registrando cada comparação.
  • Diferenciar um algoritmo O(n²), com loops aninhados, de um algoritmo O(n), com estrutura auxiliar.
  • Compreender a notação Big-O como previsão de desempenho conforme a entrada cresce.
  • Justificar a escolha de um algoritmo pelo custo que ele terá em escala real.

Solução digital

Teste de mesa (papel) + editor de pseudocódigo.

Esta atividade é de rastreamento manual: o grupo percorre os dois algoritmos no papel, anotando cada comparação — o chamado teste de mesa. O editor de pseudocódigo serve para registrar os algoritmos; o relatório é preenchido nesta página e exportado em PDF pelo navegador.

Procedimento / Atividade

Atividade proposta: Vocês são desenvolvedores júnior em uma startup. O sistema de busca do e-commerce está lento e a equipe precisa descobrir por quê. Há dois algoritmos propostos para encontrar produtos duplicados no estoque: um usa loops aninhados — O(n²), o outro usa uma estrutura auxiliar — O(n). A missão do grupo é rastrear os dois na mão, contar as comparações de cada um e entender por que um é mais eficiente. Lista de teste: [10, 20, 30, 20, 50].

Procedimentos para a realização da atividade

Checklist de entrega

Critérios de avaliação

CritérioPontos
Rastreamento correto do algoritmo O(n²) (10 comparações)3,0
Rastreamento correto do algoritmo O(n) (5 comparações)3,0
Tabela de crescimento coerente para 100 e 1.000.000 de elementos2,0
Qualidade das três respostas de reflexão2,0

Referências

  • SEDUC-SP — Roteiro de Atividade Prática SISANO1C1B2S10A3AP: “Detetives de performance”. Situação fictícia produzida pela SEDUC-SP.
  • Apostila da disciplina — Capítulos 21 a 27: laços, laços aninhados e listas.
  • CORMEN, T. H. et al. Algoritmos: teoria e prática. Rio de Janeiro: LTC — cap. 1 a 3 (análise de algoritmos e notação assintótica).
salva sozinho neste computador