Melhor, Pior & Caso Médio
Três Maneiras de Medir um Algoritmo
O custo de cada algoritmo depende de sua entrada. Duas entradas do mesmo tamanho podem produzir tempos de execução selvagemente diferentes. A análise de complexidade formaliza três perspectivas sobre essa variação.
Melhor caso — Ω (Ômega): a entrada que faz o algoritmo terminar mais rápido. Para busca linear em uma lista de N itens: Ω(1) — o alvo ocupa a primeira posição. Uma comparação, pronto.
Pior caso — O (Big O): a entrada que faz o algoritmo terminar mais lentamente. Para busca linear: O(N) — o alvo fica por último na lista, ou não aparece. Cada elemento requer inspeção.
Caso médio — Θ (Theta): custo esperado sobre todas as entradas possíveis, assumindo distribuição uniforme. Para busca linear com o alvo igualmente provável de ocupar qualquer uma das N posições: Θ(N/2) = Θ(N). A constante 1/2 desaparece porque Theta expressa crescimento assintótico aperto, não coeficientes exatos.
Por Que o Pior Caso Domina
Os sistemas devem lidar com o pior caso. Uma consulta a banco de dados que leva em média 10 ms mas ocasionalmente demora 60 segundos produz uma falha visível ao usuário. Os engenheiros projetam para limites de pior caso para que o desempenho permaneça previsível independentemente da entrada. A análise de caso médio tem valor em cenários probabilísticos, mas análise de pior caso fornece garantias.
Análise de Caso de Busca Binária
A busca binária funciona apenas em arrays ordenados. A cada passo: compare o alvo com o elemento no ponto médio. Se o alvo for igual ao ponto médio, retorne-o. Se o alvo for menor, recurse na metade esquerda. Se maior, recurse na metade direita.
Cada comparação elimina metade dos candidatos restantes.
Crescimento de Memória & Trocas entre Tempo e Espaço
Contando Memória, Não Operações
Complexidade de tempo mede o número de operações que um algoritmo executa. Complexidade de espaço mede a memória extra que ele aloca além de sua entrada. Ambas importam em sistemas de produção: um algoritmo rápido que aloca O(N²) de memória esgotará um servidor.
O(1) espaço: memória extra constante independentemente de N. Uma ordenação no local (por exemplo, ordenação por inserção) troca elementos dentro do array original. Usa alguns poucos variáveis temporárias — O(1) não importa o tamanho do array.
O(N) espaço: memória proporcional ao tamanho da entrada. Criar uma cópia de um array de N elementos requer N slots. Construir um conjunto hash a partir de uma lista de N strings armazena até N entradas.
O(N²) espaço: memória proporcional a N². Construir uma matriz de adjacência N×N para um grafo com N vértices requer N² células. Com N = 10.000 vértices, isso é 10^8 entradas — centenas de megabytes para uma grade booleana simples.
Por Que as Trocas entre Tempo e Espaço Importam
Uma das movidas fundamentais no design de algoritmos: trocar espaço por tempo, ou tempo por espaço.
Tabelas hash usam O(N) espaço extra para alcançar busca O(1). Sem a tabela hash, uma varredura em uma lista alcança busca O(N) com O(1) espaço extra. A tabela hash paga memória para comprar velocidade.
Memoização armazena resultados previamente computados (O(N) ou mais espaço) para evitar recomputá-los. Fibonacci recursivo sem memoização é executado em O(2^N) tempo. Com memoização: O(N) tempo e O(N) espaço. O investimento em espaço encolhe o tempo exponencialmente.
Dicionário Hash vs Lista Ordenada
Compare duas estratégias para contar ocorrências de palavras em um documento de N palavras:
Estratégia A: um dicionário (mapa hash). Insira cada palavra; incremente sua contagem.
Estratégia B: mantenha uma lista ordenada de palavras vistas; use busca binária para verificar associação antes de inserir.
Análise Amortizada: Distribuindo o Custo
Quando Despesa Ocasional Não Arruina o Desempenho Médio
Algumas operações são ocasionalmente custosas mas baratas em média em uma sequência. A análise amortizada calcula o custo médio por operação sobre toda a sequência — não o custo de pior caso de uma operação única.
Array dinâmico (Python list, Java ArrayList): começa com capacidade 1. Quando cheio, dobra a capacidade. Dobrar copia todos os elementos existentes: O(N) trabalho para um append. Mas dobragens são raras. Após N appends no total, quantas operações de cópia totais ocorreram?
Dobragens acontecem em tamanhos 1, 2, 4, 8, ..., N/2. Contagens de cópia: 1 + 2 + 4 + ... + N/2. Esta é uma série geométrica somando para N − 1 cópias totais entre todos os N appends. Cópias médias por append: (N − 1) / N < 1, então O(1) amortizado por append apesar de custo de pior caso O(N) por dobragem.
Por Que Análise Amortizada Importa
Um sistema que ocasionalmente pausa para redimensionar, rebalancear, ou compactar uma estrutura pode parecer ter operações individuais de pior caso alarmantes. A análise amortizada revela que o alarme é falso: os eventos raros e custosos são pagos pelos muitos baratos. Entender custo amortizado previne sobre-engenharia: adicionar complexidade para evitar uma operação O(N) rara que contribui apenas O(1) amortizado é trabalho perdido.
Indo mais fundo: O curso unhamming aplica análise de complexidade a defetos do mundo real em software de produção. Veja O Capítulo Faltante: Complexidade Algorítmica & MOAD-0001: O Defeit Sedimentar.
Inserção em Tabela Hash Amortizada
Uma tabela hash começa vazia e dobra a capacidade sempre que o fator de carga excede 0,75. Inserir 1.000 elementos dispara exatamente 10 dobragens em capacidades 1, 2, 4, 8, 16, 32, 64, 128, 256, 512.