Pular para o conteúdo

O(1) e O(n)

Aula 2 de 5 · 4 min

O(1) e O(n)

Passo 1 de 11

A mesma lista, duas tarefas: ler um slot ou procurar um valor que pode estar em qualquer lugar.

A ideia

O(1) significa que o trabalho nunca muda, não importa o tamanho da entrada. O(n) significa que você passa por cada item uma vez. Distinguir esses dois no seu próprio código é a habilidade de complexidade mais rápida de aprender.

Exemplo do mundo real

Uma máquina de venda automática é O(1): você aperta B4 e o lanche cai, tenha a máquina dez itens ou duzentos. Procurar uma marca em cada corredor do supermercado é O(n): quanto maior a loja, maior a caminhada.

O código

Sua vez

Coloque os passos em ordem.

  1. Compare o item atual com o alvo
  2. Comece pelo primeiro elemento
  3. Retorne False se a varredura inteira não encontrar nada
  4. Passe para o próximo elemento se não houver correspondência

Mini quiz

1 / 3

Qual operação é O(1)?