Ω, Θ e limites inferiores

O que O, Ω e Θ dizem de diferente — e por que nenhuma ordenação por comparação pode ser melhor que n log n.

O é um limite de cima: "não custa mais que isto". Ele sozinho não diz que um algoritmo é bom — dizer que a busca linear é O(n²) é verdade, e inútil.

A família inteira tem cinco membros, e três deles aparecem em conversa de projeto:

Do algoritmo para o problema#

A mudança de perspectiva que importa: O e Θ descrevem um algoritmo; Ω pode descrever o problema. Provar que um problema é Ω(g) é provar que nenhum algoritmo pode fazer melhor — inclusive os que ainda não foram inventados.

Quando o limite inferior do problema encontra o limite superior de um algoritmo, o assunto está encerrado: ele é ótimo, e procurar um melhor é perda de tempo.

Nenhuma ordenação por comparação vence `n log n`#

É o limite inferior mais conhecido, e a prova cabe em três linhas.

1. Ordenar n itens é escolher uma entre n! permutações possíveis.
2. Cada comparação tem dois desfechos, então k comparações distinguem no máximo 2^k casos.
3. Para 2^k ≥ n! é preciso k ≥ log₂(n!), e log₂(n!) ≈ n log n.
4. Logo, toda ordenação baseada em comparar é Ω(n log n).

O merge sort é O(n log n). Limite inferior e superior coincidem: ele é ótimo na sua classe, e nenhum truque de implementação vai derrubá-lo para O(n).

Escapar do limite: não comparar#

O limite vale para quem compara. Um algoritmo que usa o valor como endereço não está nessa classe, e por isso pode ser linear:

// ordenação por contagem: O(n + k), sem comparar nada.
// O preço: só serve para inteiros numa faixa conhecida.
action ordenar_contando(xs, maior):
    contagem := [0] * (maior + 1)
    cycle x in xs:
        contagem[x] += 1
    saida := []
    cycle valor, vezes in enumerate(contagem):
        cycle k from 1 to vezes:
            saida.append(valor)
    yield saida

out ordenar_contando([3, 1, 2, 3, 1], 3)     // [1, 1, 2, 3, 3]

Não há contradição: a contagem não é uma ordenação por comparação. Ela paga com a faixa — k entra no custo, e ordenar mil números entre 0 e um bilhão aloca um bilhão de posições.

Outros limites inferiores que decidem projeto#

Quando não se conhece nenhum algoritmo bom#

Há problemas para os quais ninguém achou solução polinomial e ninguém provou que ela não existe. Reconhecê-los é prático: significa parar de procurar o algoritmo esperto e começar a procurar uma aproximação.

// subconjunto que soma exatamente ao alvo: O(2^n) por força bruta
action soma_exata(valores, alvo, i, atual):
    given atual is alvo:
        yield yes
    given i bigger_eq len(valores) or atual bigger alvo:
        yield no
    given soma_exata(valores, alvo, i + 1, atual + valores[i]):
        yield yes
    yield soma_exata(valores, alvo, i + 1, atual)

out soma_exata([3, 34, 4, 12, 5, 2], 9, 0, 0)     // yes

Três saídas honestas, quando o problema é desses:

• Aproximar — aceitar 95% da resposta em tempo polinomial.
• Restringir — resolver só o caso que o seu sistema realmente tem (valores pequenos, grafo esparso, n abaixo de 30).
• Podar — força bruta com corte, como o atual bigger alvo acima. Não muda a classe, muda o dia.

Por onde seguir#