Melhor, Pior e Média
Três Maneiras de Medir um Algoritmo
O custo de qualquer algoritmo depende de sua entrada. Dois 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 — Ω (Omega): a entrada que faz o algoritmo terminar mais rápido. Para a busca linear sobre uma lista de N itens: Ω(1) — o alvo ocupa a primeira posição. Uma comparação, feito.
Pior caso — O (Big O): a entrada que faz o algoritmo terminar mais lentamente. Para a busca linear: O(N) — o alvo está no final da lista, ou não aparece em absoluto. Cada elemento requer inspeção.
Caso médio — Θ (Theta): custo esperado sobre todos os possíveis inputs, assumindo distribuição uniforme. Para a busca linear com o alvo igualmente provável de ocupar qualquer uma das N posições: Θ(N/2) = Θ(N). O constante 1/2 cai porque Theta expressa crescimento assintótico apertado, não coeficientes exatos.
Por que o Pior Caso Predomina
Os sistemas devem lidar com o pior caso. Uma consulta de banco de dados que tem uma média de 10 ms, mas ocasionalmente leva 60 segundos, produz uma falha perceptível para o usuário. Os engenheiros projetam para limites de pior caso para que o desempenho fique previsível independentemente da entrada. A análise de caso médio tem valor em configurações probabilísticas, mas a análise de caso de pior caso fornece garantias.
Análise de Caso de Busca Binária
A busca binária funciona apenas em arrays ordenados. A cada etapa: compare o alvo com o elemento no meio. Se o alvo for igual ao meio, retorne-o. Se o alvo for menor, recorra para a metade esquerda. Se maior, recorra para a metade direita.
Cada comparação elimina metade dos candidatos restantes.
Crescimento de Memória e Comércio de Tempo-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. Ambos importam em sistemas de produção: um algoritmo rápido que aloca O(N²) memória esgotará um servidor.
O(1) espaço: memória constante extra independentemente de N. Um algoritmo de ordenação in loco (por exemplo, ordenação de inserção) troca elementos dentro do array original. Ele usa um punhado de variáveis temporárias - O(1) independentemente do tamanho do array.
O(N) espaço: memória proporcional ao tamanho da entrada. Criando uma cópia de um array de N elementos requer N slots. Construindo um conjunto de hash a partir de uma lista de N strings armazena até N entradas.
O(N²) espaço: memória proporcional a N². Construindo uma matriz de adjacência N×N para um gráfico com N vértices requer N² células. Em N = 10.000 vértices, isso é 10^8 entradas - centenas de megabytes para uma grade booleana simples.
Comércio de Tempo-Espaço
Uma das movimentações 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 O(1) busca. Sem a tabela hash, uma busca sobre uma lista alcança O(N) busca com O(1) espaço extra. A tabela hash paga memória para comprar velocidade.
A memoização armazena resultados previamente computados (O(N) ou mais espaço) para evitar recomputá-los. Fibonacci recursivo sem memoização corre em O(2^N) tempo. Com memoização: O(N) tempo e O(N) espaço. A investimento em espaço reduz o tempo exponencial.
Dicionário Hash vs Lista Ordenada
Compare two strategies for counting word occurrences in a document of N words:
Estratégia A: um dicionário (mapa de hash). Inserir cada palavra; incrementar sua contagem.
Estratégia B: manter uma lista ordenada de palavras vistadas; usar a busca binária para verificar a pertinência antes de inserir.
Análise Amortizada: Espalhando o Custo
Quando o Gasto Ocasiona Não Ruina o Desempenho Médio
Algumas operações são ocasionalmente caras, mas baratas em média ao longo de uma sequência. A análise amortizada calcula o custo médio por operação ao longo do conjunto inteiro - não o custo pior-caso de uma única operação.
Array dinâmico (lista do Python, ArrayList do Java): começa com capacidade 1. Quando cheio, duplica a capacidade. O dobro copia todos os elementos existentes: O(N) de trabalho para uma anexação. Mas dobragens são raras. Após N inserções totais, quantas operações de cópia ocorreram no total?
Dobragens ocorrem em tamanhos 1, 2, 4, 8, ..., N/2. Contagem de cópias: 1 + 2 + 4 + ... + N/2. Essa é uma série geométrica somando N - 1 cópias totais em todos os N anexações. Média de cópias por anexação: (N - 1) / N < 1, então O(1) amortizado por anexação apesar de O(N) custo pior-caso por dobragem.
Por Que a Análise Amortizada Importa
Um sistema que ocasionalmente para para dimensionar, reequilibrar ou compactar uma estrutura pode parecer ter operações individuais com pior-caso alarmantes. A análise amortizada revela que o alarme é falso: os eventos caros ocasionais são pagos pelos muitos baratos. Compreender o custo amortizado evita o sobredimensionamento: adicionar complexidade para evitar uma rara O(N) operação que contribui apenas O(1) amortizado é trabalho desperdiçado.
Aprofundando: O curso não hamming aplica análise de complexidade a defeitos no mundo real em softwares em produção. Confira [Capítulo Faltante: Complexidade Algorítmica](/en/un/unhamming_algorithmic_complexity) & [MOAD-0001: Defeito Sedimentar](/en/un/unhamming_moad_sedimentary).
Inserção Amortizada em Tabela Hash
Uma tabela hash começa vazia e duplica sua capacidade quando o fator de carga excede 0,75. Inserindo 1.000 elementos desencadeia exatamente 10 dobragens nas capacidades de 1, 2, 4, 8, 16, 32, 64, 128, 256, 512.