Complexidade

Padrões e como melhorar

Os cinco jeitos mais comuns de escrever um O(n²) sem querer — e a versão linear de cada um.

Quase todo O(n²) acidental cai num destes cinco padrões. Os cinco têm versão linear, e as cinco usam a mesma ideia: trocar busca por indexação.

1. `in` sobre cluster dentro de laço#

O mais comum de todos. O laço está à vista; o custo do in não.

dataforge

// O(n²) — 'in' percorre 'ys' a cada item de 'xs'
action comuns_lento(xs, ys):
    saida := []
    cycle x in xs:
        given x in ys:
            saida.append(x)
    yield saida

dataforge

// O(n) — o vault responde em O(1)
action comuns(xs, ys):
    indice := {}
    cycle y in ys:
        indice[str(y)] := yes

    saida := []
    cycle x in xs:
        given indice.has(str(x)):
            saida.append(x)
    yield saida

assert comuns([1, 2, 3], [2, 3, 4]) is [2, 3]

2. Procurar dentro do laço#

dataforge

// O(n²) — 'index_of' percorre a cada volta
action posicoes_lento(xs, alvos):
    yield [xs.index_of(a) cycle a in alvos]

dataforge

// O(n) — um índice, construído uma vez
action posicoes(xs, alvos):
    onde := {}
    cycle i, x in enumerate(xs):
        given not onde.has(str(x)):
            onde[str(x)] := i
    yield [onde[str(a)] ?? -1 cycle a in alvos]

assert posicoes(["a", "b", "c"], ["c", "a"]) is [2, 0]

3. Ordenar dentro do laço#

dataforge

// O(n² log n) — ordena a cada volta
action maiores_lento(grupos):
    yield [sorted(g)[-1] cycle g in grupos]

dataforge

// O(n) — 'max' não precisa ordenar
action maiores(grupos):
    yield [max(g) cycle g in grupos]

assert maiores([[3, 1], [5, 9]]) is [3, 9]

Ordenar para pegar o maior é pagar O(n log n) por uma resposta que custa O(n). Vale só quando se quer os k maiores, com k grande.

4. Concatenar dentro do laço#

dataforge

// O(n²) — cada '+' copia a string inteira
action juntar_lento(partes):
    saida := ""
    cycle p in partes:
        saida := saida + p
    yield saida

dataforge

// O(n) — 'join' aloca uma vez
action juntar(partes):
    yield "".join(partes)

assert juntar(["a", "b", "c"]) is "abc"

Vale para clusters também: saida := [...saida, x] dentro de um laço copia tudo a cada volta. Use saida.append(x), que é O(1) amortizado.

5. Agrupar comparando todos com todos#

dataforge

// O(n²) — compara cada um com cada um
action agrupar_lento(itens):
    grupos := []
    cycle item in itens:
        achou := no
        cycle g in grupos:
            given g[0]["tipo"] is item["tipo"]:
                g.append(item)
                achou := yes
        given not achou:
            grupos.append([item])
    yield grupos

dataforge

// O(n) — o vault agrupa direto
action agrupar(itens):
    yield itens.group_by(lambda i: i["tipo"])

dados := [{"tipo": "a", "n": 1}, {"tipo": "a", "n": 2}, {"tipo": "b", "n": 3}]
assert len(agrupar(dados)["a"]) is 2

A ideia por trás dos cinco#

O custo é memória: o índice ocupa O(n). Ver complexidade de espaço para quando essa troca não vale.

Encontrando os seus#

bash

dataforge big-o src/ -v | grep -A3 'O(n^2)'

Ou deixe o editor mostrar: a extensão marca com ⟵ acima do limite tudo o que passa de O(n log n).