Eficiência e complexidade

Certo não basta — precisa escalar

Imagine procurar um nome numa agenda telefônica. Você pode olhar página por página, do começo ao fim (lento), ou abrir no meio e ir cortando metade a cada vez (rapidíssimo). As duas estratégias funcionam — mas, conforme a agenda cresce, a diferença entre elas se torna gigantesca.

Por isso, em computação, não basta perguntar "funciona?". Perguntamos: como o custo cresce quando os dados aumentam?

Veja as curvas explodirem

Arraste o n (tamanho da entrada) e observe quantas operações cada tipo de algoritmo precisa. Repare como o O(n²) dispara enquanto o O(log n) mal sai do lugar:

É essa diferença de crescimento — não o número exato — que a notação Big O captura.

Notação Big O

Big O descreve como o número de operações cresce em função de n, ignorando constantes e detalhes de máquina. O(2n) e O(n) são a mesma classe: o que importa é a forma do crescimento.

          n=10      n=1.000        n=1.000.000
O(1)        1         1              1
O(log n)    ~3        ~10            ~20
O(n)        10        1.000          1.000.000
O(n log n)  ~33       ~10.000        ~20.000.000
O(n²)       100       1.000.000      1.000.000.000.000

Olhe a última coluna: para um milhão de itens, um algoritmo O(n²) faz um trilhão de operações — inviável. O O(n log n) faz vinte milhões. Mesma resposta, mundos diferentes.

Tempo vs. memória, e os três casos

• Tempo (quantas operações) e memória (quanto espaço) — às vezes troca-se um pelo outro.
• Melhor / médio / pior caso: a busca linear pode achar no 1º item (melhor) ou só no último (pior).

Contando operações você mesmo

função buscaLinear(lista, alvo):
    operacoes = 0
    para cada item na lista:
        operacoes += 1
        se item == alvo:
            retorne operacoes   # achou!
    retorne operacoes              # pior caso: olhou tudo

Meça de verdade

Mini projeto: adicione um contador de operações a um laço e veja o número subir conforme a entrada cresce.

Projeto principal: compare busca linear e busca binária na mesma lista ordenada, contando os passos de cada uma.

Desafio extra: meça o tempo real (em ms) de ordenar listas de 1.000, 10.000 e 100.000 itens e veja a curva aparecer.

Teste sua intuição

Onde você encontra isso