⏱️ O que é Complexidade?

O que é Complexidade?

Imagine que você tem uma tarefa simples: encontrar uma pessoa específica em uma lista de usuários. Se a lista tem 10 pessoas, você encontra rapidamente. Mas e se forem 1 bilhão de perfis, como em uma rede social? O esforço para encontrar alguém pode mudar completamente dependendo da forma como você procura.

A complexidade de um algoritmo estuda como o consumo de recursos, principalmente tempo e memória, muda à medida que aumentamos o tamanho da entrada. Quando escrevemos um algoritmo, não basta saber se ele funciona. Precisamos entender se ele continua viável quando a quantidade de dados cresce.

• Complexidade de Tempo: quantos passos o algoritmo executa em função do tamanho da entrada n.
• Complexidade de Espaço: quanta memória extra o algoritmo precisa alocar para executar, além do espaço já ocupado pelos dados de entrada.

Neste primeiro momento, pense em complexidade como uma forma de relacionar o tamanho da entrada com o trabalho que o algoritmo precisa fazer.

Um exemplo prático: a busca simples

Imagine que queremos saber se um número específico está dentro de uma lista.

def find_item(items, target):
    for item in items:
        if item == target:
            return True
    return False

Para entender a complexidade, não olhamos para a sintaxe da linguagem, mas para o esforço necessário para executar o algoritmo:

1. Se a lista items tem 10 elementos, o computador faz, no pior caso, 10 comparações.
2. Se a lista items tem 1 milhão de elementos, ele faz, no pior caso, 1 milhão de comparações.
3. Se a lista items dobrar de tamanho, o trabalho também dobra.

Essa relação entre o tamanho do problema e o esforço para resolvê-lo é o que queremos estudar.

Chamamos de pior caso o cenário em que o algoritmo precisa trabalhar o máximo possível.

Por exemplo, ao procurar um número em uma lista:

• Se o número estiver no começo, encontramos rápido.
• Mas se ele estiver no final (ou nem existir), precisamos olhar todos os elementos (pior caso).

A mudança de mentalidade: tempo de relógio vs. passos lógicos

Um erro comum é tentar medir a eficiência usando um cronômetro, em segundos ou milissegundos. Isso parece intuitivo, mas pode enganar.

• Hardware: um computador mais potente executa o mesmo código mais rápido.
• Linguagem: algumas linguagens têm implementações mais rápidas para certas tarefas.
• Ambiente: processos em segundo plano podem afetar o tempo medido.

Por isso, ignoramos o tempo exato de relógio e focamos no número de operações fundamentais.

Em outras palavras: a complexidade não mede o tempo absoluto, mas sim como o trabalho muda quando a entrada aumenta.

Por que isso importa?

Se um algoritmo é ineficiente, não adianta apenas usar uma máquina melhor. Quando o volume de dados cresce, o esforço pode crescer junto e tornar a solução inviável.

Entender complexidade nos ajuda a prever esse comportamento antes de o problema aparecer em produção.

Por que as Big Techs perguntam sobre complexidade?

Em uma entrevista, o entrevistador quer saber se você consegue prever como seu código se comportará com milhões de usuários.

Saber explicar a complexidade do seu algoritmo demonstra que você pensa em escalabilidade, e não apenas em fazer o código funcionar para casos pequenos.

No próximo capítulo, vamos transformar essa ideia de "crescimento" em uma notação matemática chamada Big‑O, que nos permite comparar algoritmos de forma padronizada.