</>Codding
Estruturas de Dados & Algoritmos0/24 lições

Módulo 1 • Complexidade

Notação Big-O

Ferramentas e leitura
Leitura100%
Aula guiada50–75 min5 etapas práticas

Nesta aula, você vai compreender Notação Big-O com explicação progressiva, exemplo resolvido, checagens e prática. Nada de apenas copiar: cada etapa prepara a próxima.

Antes de começar: Leia a aula anterior do módulo se algum termo parecer novo. Você pode testar o exemplo antes de continuar.

Ao terminar, você vai conseguir

  • Explicar Notação Big-O com suas próprias palavras
  • Reconhecer as partes importantes em um exemplo real
  • Identificar e corrigir os erros mais frequentes
  • Aplicar o conteúdo em uma atividade prática
1

Entrada

Reconheça os dados e condições disponíveis.

2

Processamento

Use Notação Big-O para transformar a entrada.

3

Saída

Confira o resultado e os casos que podem falhar.

0/6 atividades
1

Entenda o problema

O que é Notação Big-O

Big-O descreve como o custo de um algoritmo cresce quando a entrada cresce. Não mede segundos: mede a forma da curva — e é isso que decide se seu código aguenta 10 mil usuários.

Cheque seu entendimento

O que O(n²) costuma indicar no código?

1 de 5

O que você aprendeu

  • Big-O descreve como o custo de um algoritmo cresce quando a entrada cresce. Não mede segundos: mede a forma da curva — e é isso que decide se seu código aguenta 10 mil usuários.
  • As duas funções fazem a mesma coisa. A segunda troca tempo por um pouco de memória e sai de O(n²) para O(n).
  • Evite: Colocar uma busca em lista (O(n)) dentro de um laço — vira O(n²) sem você perceber.
  • Evite: Otimizar antes de medir: o gargalo quase nunca está onde você acha.

Videoaulas sobre este tema

Se você aprende melhor assistindo, abrimos uma seleção de aulas em vídeo em português sobre exatamente este assunto.

Aula em vídeo sobre este temaVídeos em português explicando "Notação Big-O" passo a passo.Vendo alguém programar issoExemplos práticos, com o código sendo escrito na tela.Playlist completa de Estruturas de Dados & AlgoritmosCurso em vídeo do começo ao fim, para acompanhar junto com o módulo "Complexidade".

Quiz rápido

0/2 • 0 certas

1. O que O(n²) costuma indicar no código?

2. Por que 3n + 50 é considerado O(n)?

Laboratório

1/4

1. Faça funcionar

Laboratório de Notação Big-O: execute o exemplo, identifique entrada, processamento e saída e altere pelo menos um valor para observar como o resultado muda.

Abrir no playground
  • Checkpoints da prática (1/4)
  • Escreva sua versão a partir do modeloO texto do editor ainda é igual ao modelo inicial. Altere pelo menos uma linha para que a prática conte como sua.
  • Nenhuma lacuna deixada em branco
  • Execute seu códigoClique em “Verificar resposta” para rodar seu código e comparar a saída com o esperado.
  • Resultado ainda não confereEsperado: o programa rodar sem erro. Se aparecer uma mensagem de erro, leia a última linha: ela indica a linha e o tipo do problema.

Escreva sua solução e clique em Verificar.

Tire sua dúvida

Cada resposta é conferida contra o material desta lição antes de aparecer. Sem IA por trás e sem inventar nada.

Notação Big-O

Estruturas de Dados & Algoritmos • Módulo 1: Complexidade • Codding — material para estudo offline

Aluno: ______________________________ Data: ____ / ____ / ______

Nesta aula, você vai compreender Notação Big-O com explicação progressiva, exemplo resolvido, checagens e prática. Nada de apenas copiar: cada etapa prepara a próxima.

Objetivos da aula

  • Explicar Notação Big-O com suas próprias palavras
  • Reconhecer as partes importantes em um exemplo real
  • Identificar e corrigir os erros mais frequentes
  • Aplicar o conteúdo em uma atividade prática

Pré-requisito: Leia a aula anterior do módulo se algum termo parecer novo. Você pode testar o exemplo antes de continuar. • Duração: 50–75 min

Explicação passo a passo

1. O que é Notação Big-O

Big-O descreve como o custo de um algoritmo cresce quando a entrada cresce. Não mede segundos: mede a forma da curva — e é isso que decide se seu código aguenta 10 mil usuários.

Checkpoint: O que O(n²) costuma indicar no código? — Resposta: Laços aninhados sobre a mesma entrada

2. Como pensar antes de fazer

O(1) não depende do tamanho (acessar índice, ler chave de dicionário). O(n) percorre tudo uma vez. O(n log n) é o teto dos bons algoritmos de ordenação. O(n²) são laços aninhados — aceitável em 100 itens, desastre em 100 mil.

Dica: Não decore a forma. Tente explicar com suas palavras qual problema “Notação Big-O” resolve.

3. Exemplo completo, do início ao resultado

Constantes e termos menores somem: 3n + 50 é O(n). O que importa é o termo dominante, porque é ele que manda quando o dado cresce.

# O(n): um laço sobre a entrada
def tem_duplicado_lento(lista):
    for i in range(len(lista)):
        for j in range(i + 1, len(lista)):   # laço dentro de laço => O(n²)
            if lista[i] == lista[j]:
                return True
    return False

# O(n): um conjunto resolve com uma passada
def tem_duplicado(lista):
    vistos = set()
    for item in lista:
        if item in vistos:      # busca O(1)
            return True
        vistos.add(item)
    return False
TrechoO que faz
# O(n): um laço sobre a entradaComentário de orientação: documenta a intenção sem executar uma ação.
def tem_duplicado_lento(lista):Cria uma estrutura reutilizável para organizar comportamento.
for i in range(len(lista)):Percorre ou transforma uma sequência de valores.
for j in range(i + 1, len(lista)): # laço dentro de laço => O(n²)Percorre ou transforma uma sequência de valores.
if lista[i] == lista[j]:Decide qual caminho será executado de acordo com uma condição.
return TrueProduz ou devolve o resultado que permite conferir a execução.
return FalseProduz ou devolve o resultado que permite conferir a execução.
# O(n): um conjunto resolve com uma passadaComentário de orientação: documenta a intenção sem executar uma ação.

Dica: As duas funções fazem a mesma coisa. A segunda troca tempo por um pouco de memória e sai de O(n²) para O(n).

Checkpoint: Por que 3n + 50 é considerado O(n)? — Resposta: Porque o que importa é o termo dominante quando a entrada cresce

4. Do detalhe para o todo

Custo de memória conta também. Criar uma cópia da lista dentro de um laço é O(n²) de tempo e memória escondido em código que parece inocente.

5. Erros comuns e como corrigi-los

1. Colocar uma busca em lista (O(n)) dentro de um laço — vira O(n²) sem você perceber. 2. Otimizar antes de medir: o gargalo quase nunca está onde você acha. 3. Confundir 'rápido na minha máquina com 10 itens' com 'escala'.

Dica: Quando algo der errado, compare uma diferença por vez com o exemplo. Evite mudar várias partes ao mesmo tempo.

Prática guiada

1. 1. Faça funcionar

Laboratório de Notação Big-O: execute o exemplo, identifique entrada, processamento e saída e altere pelo menos um valor para observar como o resultado muda.

# O(n): um laço sobre a entrada
def tem_duplicado_lento(lista):
    for i in range(len(lista)):
        for j in range(i + 1, len(lista)):   # laço dentro de laço => O(n²)
            if lista[i] == lista[j]:
                return True
    return False

# O(n): um conjunto resolve com uma passada
def tem_duplicado(lista):
    vistos = set()
    for item in lista:
        if item in vistos:      # busca O(1)
            return True
        vistos.add(item)
    return False

Dica: Volte ao exemplo resolvido e compare a estrutura. Colocar uma busca em lista (O(n)) dentro de um laço — vira O(n²) sem você perceber.

2. 2. Preveja antes de testar

Sem executar, explique qual resultado o exemplo de Notação Big-O deve produzir e qual parte é responsável por ele.

Minha previsão:

A parte responsável pelo resultado:

Como vou conferir:

Dica: Use o modelo mental da aula: entrada, transformação e evidência observável.

3. 3. Encontre e corrija o erro

Use o exemplo de Notação Big-O, identifique um risco citado na aula e registre ou implemente a correção.

# O(n): um laço sobre a entrada
def tem_duplicado_lento(lista):
    for i in range(len(lista)):
        for j in range(i + 1, len(lista)):   # laço dentro de laço => O(n²)
            if lista[i] == lista[j]:
                return True
    return False

# O(n): um conjunto resolve com uma passada
def tem_duplicado(lista):
    vistos = set()
    for item in lista:
        if item in vistos:      # busca O(1)
            return True
        vistos.add(item)
    return False

Dica: Colocar uma busca em lista (O(n)) dentro de um laço — vira O(n²) sem você perceber.

4. 4. Aplique em um caso novo

Crie uma variação própria usando Notação Big-O. Mude os dados ou o cenário e demonstre que o resultado continua correto.

# O(n): um laço sobre a entrada
def tem_duplicado_lento(lista):
    for i in range(len(lista)):
        for j in range(i + 1, len(lista)):   # laço dentro de laço => O(n²)
            if lista[i] == lista[j]:
                return True
    return False

# O(n): um conjunto resolve com uma passada
def tem_duplicado(lista):
    vistos = set()
    for item in lista:
        if item in vistos:      # busca O(1)
            return True
        vistos.add(item)
    return False

Dica: Mantenha a estrutura que já funcionou e altere uma decisão por vez.

Revisão

  • Big-O descreve como o custo de um algoritmo cresce quando a entrada cresce. Não mede segundos: mede a forma da curva — e é isso que decide se seu código aguenta 10 mil usuários.
  • As duas funções fazem a mesma coisa. A segunda troca tempo por um pouco de memória e sai de O(n²) para O(n).
  • Evite: Colocar uma busca em lista (O(n)) dentro de um laço — vira O(n²) sem você perceber.
  • Evite: Otimizar antes de medir: o gargalo quase nunca está onde você acha.

Exemplo comentado

# O(n): um laço sobre a entrada
def tem_duplicado_lento(lista):
    for i in range(len(lista)):
        for j in range(i + 1, len(lista)):   # laço dentro de laço => O(n²)
            if lista[i] == lista[j]:
                return True
    return False

# O(n): um conjunto resolve com uma passada
def tem_duplicado(lista):
    vistos = set()
    for item in lista:
        if item in vistos:      # busca O(1)
            return True
        vistos.add(item)
    return False

As duas funções fazem a mesma coisa. A segunda troca tempo por um pouco de memória e sai de O(n²) para O(n).

Erros comuns

  • Colocar uma busca em lista (O(n)) dentro de um laço — vira O(n²) sem você perceber.
  • Otimizar antes de medir: o gargalo quase nunca está onde você acha.
  • Confundir 'rápido na minha máquina com 10 itens' com 'escala'.

Quiz e gabarito completo

  1. 1. O que O(n²) costuma indicar no código?

    • a) Uso de recursão
    • b) Laços aninhados sobre a mesma entrada
    • c) Muitas variáveis
    • d) Uso de dicionário

    Gabarito: b) Laços aninhados sobre a mesma entrada — Cada item da entrada sendo comparado com todos os outros gera crescimento quadrático.

  2. 2. Por que 3n + 50 é considerado O(n)?

    • a) Porque 50 é pequeno
    • b) Porque o que importa é o termo dominante quando a entrada cresce
    • c) Porque n é sempre maior que 50
    • d) Porque constantes não existem

    Gabarito: b) Porque o que importa é o termo dominante quando a entrada cresce — Big-O descreve a forma do crescimento, não o valor exato.

Codding • Estruturas de Dados & Algoritmos • Notação Big-O • Prova final e certificado em codding.lovable.app/cursos/estruturas-de-dados/prova