Complexidade

Analisar o seu código

O comando, o que ele prova, e o que ele honestamente não prova.

dataforge big-o lê a árvore do programa e conta estrutura: quantos laços aninhados, se o contador dobra ou soma, quantas vezes uma ação chama a si mesma, e quanto custa cada função embutida que aparece.

bash

dataforge big-o programa.df           # a classe de cada ação
dataforge big-o src/ -v              # com o porquê e a sugestão
dataforge big-o src/ --strict        # sai com erro acima de O(n log n)
dataforge big-o --escala             # a tabela de referência
dataforge big-o programa.df --json   # para o editor e o CI

No editor#

A extensão do VS Code mostra a classe acima de cada ação, enquanto se escreve. O motivo aparece no hover, e o comando Analisar complexidade abre o relatório completo.

É a mesma análise: a extensão chama a CLI. O que o editor mostra é exatamente o que o CI vai reprovar.

O que ele detecta#

Padrão	Classe	Como reconhece
`cycle x in xs`	O(n)	uma volta por item
dois `cycle` aninhados	O(n²)	multiplica as ordens
`persist` com `n ~/ 2`	O(log n)	a variável se divide a cada volta
`persist` com `n -= 1`	O(n)	avança de um em um
`cycle i from 1 to 10`	O(1)	limites constantes
`sorted(xs)`	O(n log n)	custo conhecido da embutida
`x in xs`	O(n)	percorre o cluster
`v.has(k)`	O(1)	vault indexa
uma chamada recursiva, `n - 1`	O(n)	profundidade linear
uma chamada recursiva, `n ~/ 2`	O(log n)	profundidade logarítmica
duas chamadas, `n - 1`	O(2ⁿ)	ramifica sem dividir
duas chamadas, metade cada	O(n log n)	divisão e conquista
compreensão aninhada	O(n²)	cabe numa linha e é um laço duplo

A distinção que mais importa#

Merge sort e fibonacci ingênuo têm a mesma forma: uma ação que chama a si mesma duas vezes. O que os separa é a entrada — metade contra n−1:

dataforge

// duas chamadas sobre METADE  →  O(n log n)
action merge_sort(xs):
    given len(xs) smaller_eq 1:
        yield xs
    meio := len(xs) ~/ 2
    yield intercalar(merge_sort(xs[:meio]), merge_sort(xs[meio:]))

// duas chamadas sobre n-1  →  O(2^n)
action fib(n):
    given n smaller 2:
        yield n
    yield fib(n - 1) + fib(n - 2)

Confundir os dois condenaria todo algoritmo de divisão e conquista. A análise olha o argumento da chamada recursiva para separá-los.

Generators têm custo por item#

Um stream action com persist yes não é um laço infinito por engano — é uma sequência preguiçosa, e quem consome decide quantos itens quer. A análise reporta o custo por item emitido:

dataforge

stream action naturais():
    n := 0
    persist yes:
        emit n
        n += 1

out naturais().take(5)

naturais é O(1) por item. Analisar o corpo inteiro daria O(?) para todo generator correto da linguagem.

O que ele não faz#

Três limites, declarados de propósito:

Não decide o indecidível. Saber se um laço termina é o problema da parada. Quando a análise não consegue provar, ela diz O(?) em vez de inventar um número.
Não segue valor. cycle i from 1 to k é O(k). Se k vier de fora, ela usa k como símbolo em vez de fingir que é constante.
Não mede constante. O(n) com constante grande pode ser mais lento que O(n²) para entrada pequena.

No CI#

--strict faz o comando sair com código 1 se alguma ação passar de O(n log n). É o suficiente para uma regra de projeto:

text

# .github/workflows/ci.yml
- name: complexidade
  run: dataforge big-o src/ --strict

Use com julgamento: há problemas cuja melhor solução conhecida é quadrática. A regra serve para o quadrático acidental, que é a maioria.