Toda Classe de Complexidade Desenha uma Curva
Plotando Custo contra Tamanho de Entrada
Coloque o tamanho de entrada N no eixo x. Coloque o custo (operações, tempo) no eixo y. Cada classe de complexidade produz uma curva distinta. Você pode reconhecer a taxa de crescimento de um algoritmo pela forma de sua curva de desempenho.
O(1) — linha horizontal plana. A função f(N) = 1. Nenhuma inclinação. O custo nunca muda independentemente de N. Busca em tabela hash: seja a tabela contendo 10 ou 10.000.000 elementos, um cálculo hash salta para o balde correto.
O(log N) — curva suave para cima, inclinação decrescente. Em N = 1.000.000: custo ≈ 20 operações. A curva sobe abruptamente para N pequeno, depois se achata. Cada duplicação de N adiciona exatamente uma unidade de custo.
O(N) — linha reta diagonal. Inclinação = 1 (no sentido assintótico). O custo cresce na mesma taxa que N. Se N triplicar, o custo triplicará.
O(N log N) — diagonal mais acentuada com curvatura para cima leve. Fica acima de O(N) mas abaixo de O(N²). O fator log adiciona um multiplicador que cresce lentamente à inclinação linear.
O(N²) — parábola abrindo para cima. A inclinação aumenta conforme N cresce. Em N = 10: custo = 100. Em N = 100: custo = 10.000. Em N = 1.000: custo = 1.000.000.
O Hiato em Crescimento
A razão O(N²) / O(N) = N. O hiato entre a parábola e a diagonal se amplia conforme N cresce. Em N = 10: hiato de 10×. Em N = 100: hiato de 100×. Em N = 1.000: hiato de 1.000×. Em N = 50.000: hiato de 50.000×. O hiato é igual a N — sempre.
Calculando o Hiato de Escala
Um grande gráfico de dependência contém 50.000 pacotes (N = 50.000). Um algoritmo é executado em tempo O(N). Um segundo é executado em O(N²). Neste N, a razão O(N²)/O(N) = N = 50.000.
Bisectando um Segmento de Linha
Busca Binária como Bisecção Repetida
Um array ordenado de N elementos forma um segmento de linha de comprimento N. A busca binária repete-se bisectando este segmento:
1. Aponte para o ponto médio do segmento restante.
2. Se alvo < ponto médio: a metade direita desaparece. Recurse na metade esquerda.
3. Se alvo > ponto médio: a metade esquerda desaparece. Recurse na metade direita.
4. Se alvo = ponto médio: feito.
Após k bisecções, o segmento restante tem comprimento N / 2^k. A busca termina quando esse comprimento é igual a 1:
N / 2^k = 1 → 2^k = N → k = log₂N
Então a busca binária em N elementos requer no máximo log₂N comparações.
Redução & Duplicação: Dois Lados da Mesma Curva
Redução e duplicação são inversos geométricos. A curva exponencial 2^k e a curva logarítmica log₂N são reflexões uma da outra através da linha y = x.
Considere a dobragem de papel: uma folha começa com 0,1 mm de espessura. Cada dobra duplica a espessura. Após 42 dobras: 0,1 mm × 2^42 ≈ 439.804 km — passando a lua (384.400 km). A busca binária executa o inverso: começar com N elementos, cada passo reduz o número pela metade, alcançar 1 elemento em log₂N passos.
A geometria: bisecção é uma operação auto-similar. Cada bisecção produz duas metades que parecem idênticas em estrutura ao todo. Recursão e logaritmos compartilham essa auto-similaridade.
Comparações & Duplicações
Um array ordenado contém 1.048.576 elementos. Nota: 1.048.576 = 2^20.
Uma Função Hash como um Mapa Geométrico
Função Hash como Função
Uma tabela hash mapeia uma chave para um balde usando uma função hash:
bucket = hash(key) mod table_size
Esta é uma função no sentido matemático estrito: ela mapeia um domínio (todas as chaves possíveis) para um intervalo (índices de balde 0 a table_size − 1). A imagem geométrica: as chaves ocupam um espaço; os baldes ocupam outro. A função hash projeta as chaves nos índices de balde.
Busca O(1) — salto direto, sem busca. A função hash calcula o índice do balde em tempo constante. Salte diretamente para esse balde. Sem travessia, sem loop de comparação.
Fator de carga. Em fator de carga 0,75, 75% dos baldes contêm pelo menos um elemento. Acima de ~0,9, colisões aumentam: duas chaves fazem hash para o mesmo balde, formando uma cadeia de elementos dentro daquele balde. Busca em uma cadeia longa se degrada para O(N) no pior caso.
Qualidade de Distribuição como Geometria
Uma função hash bem-distribuída espalha as chaves uniformemente entre todos os baldes. Geometricamente: o intervalo da função cobre seu codomínio uniformemente. Cada balde recebe aproximadamente N / table_size chaves.
Uma função hash pobre agrupa as chaves em alguns baldes. Geometricamente: o intervalo da função se colapsa para um subconjunto do codomínio — a maioria das chaves mapeia para os mesmos poucos pontos. Os baldes restantes ficam vazios.
Conexão com MOAD-0001
Substituir uma lista por um conjunto conserta MOAD-0001 porque um conjunto usa uma tabela hash internamente. Varredura de lista O(N) → busca de tabela hash O(1). Geometricamente: travessia linear ao longo de uma sequência se transforma em uma projeção direta via uma função. A sequência desaparece; a função a substitui.
Analisando um Hash Distribuído Inadequadamente
Uma tabela hash tem 1.000 baldes e 900 elementos (fator de carga 0,9). Uma função hash pobre envia 500 desses elementos para o mesmo balde.