O(1) e O(n)
Passo 1 de 11
O(1) ops0O(n) ops0
nums[0] · O(1)
hit
7
3
9
1
8
5
6
42
contains(42) · O(n)
i
7
3
9
1
8
5
6
42
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.
- Compare o item atual com o alvo
- Comece pelo primeiro elemento
- Retorne False se a varredura inteira não encontrar nada
- Passe para o próximo elemento se não houver correspondência
Mini quiz
1 / 3