📊 Casos de Análise (melhor, médio, pior)

Notações como O, Θ e Ω descrevem crescimento. Também é importante responder uma pergunta fundamental:

o algoritmo se comporta sempre do mesmo jeito?

A resposta é: nem sempre.

Dependendo da entrada, a quantidade de trabalho pode mudar bastante. Por isso, analisamos algoritmos em diferentes casos.

O que são casos de análise?

Casos de análise são diferentes cenários de execução de um mesmo algoritmo.

Os três mais comuns são:

• Melhor caso: a entrada mais favorável possível
• Caso médio: o comportamento esperado em entradas "típicas"
• Pior caso: a entrada mais desfavorável possível

Esses casos não mudam o algoritmo. O que muda é a situação em que ele está sendo executado.

Exemplo clássico: busca linear

Considere este algoritmo:

def encontrar_item(lista, alvo):
    for item in lista:
        if item == alvo:
            return True
    return False

Esse algoritmo percorre a lista até encontrar o valor desejado ou até acabar a lista.

Melhor caso

O melhor caso acontece quando o alvo está logo no primeiro elemento.

Nesse cenário, o algoritmo faz apenas 1 comparação.

Podemos descrever esse caso como:

Θ(1)

Pior caso

O pior caso acontece quando:

• o alvo está no último elemento, ou
• o alvo não está na lista

Nesse cenário, o algoritmo precisa percorrer toda a entrada.

Podemos descrever esse caso como:

Θ(n)

Caso médio

O caso médio representa o comportamento esperado para entradas comuns. Na busca linear, em uma visão simplificada, isso costuma significar olhar aproximadamente metade da lista antes de encontrar o alvo.

Mesmo assim, o crescimento continua sendo proporcional a n.

Por isso, o caso médio também é linear:

Θ(n)

Por que o pior caso aparece tanto?

Em muitos contextos, usamos o pior caso porque ele oferece uma garantia.

Se dizemos que um algoritmo é O(n²) no pior caso, estamos dizendo:

"mesmo na situação mais desfavorável, ele não cresce mais do que isso."

Essa visão é útil porque:

• ajuda a evitar surpresas
• facilita comparar soluções
• dá uma noção de segurança sobre o limite de custo

Isso não significa que o algoritmo sempre atinge o pior caso. Significa apenas que esse é o teto mais relevante para a análise escolhida.

Melhor caso pode enganar

Olhar só para o melhor caso pode passar uma impressão otimista demais.

Volte ao exemplo da busca linear:

• melhor caso: encontra de primeira
• pior caso: percorre toda a lista

Se eu analisar apenas o melhor caso, posso concluir que a busca linear é "rápida". Mas isso esconde o fato de que, em muitas entradas, ela ainda pode precisar percorrer quase tudo.

Caso médio exige mais cuidado

O caso médio parece intuitivo, mas costuma ser mais difícil de calcular com precisão.

Para fazer uma análise média rigorosa, normalmente precisamos assumir algo sobre a distribuição das entradas:

• quais entradas são mais prováveis?
• todas acontecem com a mesma frequência?
• o valor procurado costuma existir ou não?

Sem esse contexto, o "caso médio" pode virar apenas um chute.

Por isso, em conteúdos introdutórios, o pior caso costuma aparecer mais.

Outro exemplo: verificar duplicatas

Considere uma estratégia simples:

def tem_duplicata(lista):
    for i in range(len(lista)):
        for j in range(i + 1, len(lista)):
            if lista[i] == lista[j]:
                return True
    return False

Melhor caso

Se os primeiros elementos já formarem uma duplicata, o algoritmo para cedo.

Nesse caso, ele pode fazer poucas comparações.

Pior caso

Se não houver duplicatas, ele precisará testar muitas combinações.

Esse é o cenário mais caro.

O detalhe importante aqui é: um algoritmo pode parar cedo em algumas entradas e ainda assim ter um pior caso bem mais pesado.

Como isso se conecta com O, Ω e Θ?

As notações e os casos se combinam.

Por exemplo, podemos dizer:

• "a busca linear tem pior caso O(n)"
• "a busca linear tem melhor caso Ω(1)"
• "o pior caso desse algoritmo é Θ(n²)"

O importante é sempre deixar claro de qual caso você está falando.

Sem isso, a análise pode ficar ambígua.

Resumo

• Um mesmo algoritmo pode ter custos diferentes dependendo da entrada.
• Os principais casos são: melhor, médio e pior.
• O pior caso é muito usado porque oferece uma garantia.
• O melhor caso isolado pode ser enganoso.
• O caso médio costuma exigir hipóteses adicionais sobre as entradas.

Comparar diferentes classes de crescimento ajuda a perceber quais algoritmos continuam viáveis quando a entrada aumenta.