Como funciona o Big O Analyzer
Entenda o pipeline de análise por trás do resultado.
Visão geral
O Big O Analyzer usa um pipeline de análise estática para estimar a complexidade de tempo do código sem executá-lo.
Esse pipeline é dividido em estágios, cada um enriquecendo a análise anterior até chegar a uma classificação final de complexidade.
Pipeline de análise
Código-fonte → AST
O código é convertido em uma Árvore de Sintaxe Abstrata (AST), com nós representando estruturas como funções, loops e condicionais.
- Remoção de comentários e strings para reduzir falsos positivos
- Tokenização por regex e palavras-chave
- Geração de uma AST específica para cada linguagem
- Coleta de metadados relevantes (nome de função, posição, etc.)
O parser é leve: foca em estrutura, não em todos os detalhes da linguagem.
AST → IR
Transforma a AST em uma Representação Intermediária (IR) agnóstica de linguagem.
- Mapeia nós específicos para tipos genéricos (FUNCTION_DEF, LOOP, CONDITIONAL, CALL, STATEMENT)
- Preserva nomes de funções e informações de escopo
- Gera uma lista plana de nós IR com IDs estáveis
- howItWorks.pipeline.stage2.points.3
IR → Grafo básico
Constrói um grafo base de fluxo de execução a partir do IR.
- Criação de nós de entrada (ENTRY) e saída (EXIT)
- Conexão sequencial de nós, refletindo a ordem de execução
- Preparação para enriquecer o grafo com estruturas de controle no próximo estágio
Esse grafo é a base para entender o fluxo do programa.
Grafo de fluxo de controle completo
Enriquece o grafo com estruturas de decisão e repetição.
- Ramificações para condicionais (true/false)
- Arestas de volta para loops
- Marcação de pontos de entrada e saída em blocos condicionais
Com isso, é possível:
- Contar loops e profundidade de aninhamento
- Detectar recursão
- Identificar caminhos mais custosos
Loops e recursão
Um analisador de limites passa pelo código para entender quantas vezes cada parte pode executar.
- Detecção de loops e cálculo de profundidade máxima
- Detecção de padrões de recursão por nome de função
- Identificação de hints de dividir e conquistar (particionamentos, divisão por 2, etc.)
- Reconhecimento de padrões específicos como busca binária
O resultado é um objeto com informações de laços, recursão e profundidade que alimentam a etapa final.
Classificação final
Combina todos os dados anteriores para chegar a um Big O final.
- Reconhecimento de chamadas nativas com complexidade conhecida
- Matching de padrões (busca binária, sorts clássicos, etc.)
- Análise de recursões exponenciais e fatoriais
- Uso da profundidade de loops e das ramificações para estimar O(n), O(n²), O(n log n)…
- howItWorks.pipeline.stage6.points.4
Saída: uma única classe de pior caso (O(1), O(n), O(n log n), O(n²), O(2ⁿ), O(n!) etc.).
Reconhecimento de padrões
Além da estrutura, o analisador tenta reconhecer algoritmos e chamadas típicas.
Alguns métodos de biblioteca têm complexidades bem conhecidas:
- JavaScript: .sort(), .map(), .filter()…
- Python: sorted(), heapq, bisect…
- Java: Collections.sort(), Arrays.sort(), etc.
Entre os padrões reconhecidos, estão:
- Busca binária (left/right/mid)
- Merge sort
- Quick sort (particionamento)
- Loops aninhados
- Backtracking recursivo
Exemplo: busca binária
Um exemplo simplificado de como o código é processado:
function binarySearch(arr, target) {
let left = 0, right = arr.length - 1;
while (left <= right) {
const mid = Math.floor((left + right) / 2);
if (arr[mid] === target) return mid;
if (arr[mid] < target) left = mid + 1;
else right = mid - 1;
}
return -1;
}Parsing
Identifica a função, o loop while e as condicionais.
Normalização
Transforma nodes da AST em nós FUNCTION_DEF, LOOP, CONDITIONAL no IR.
CFG
Cria o grafo com uma aresta de volta no loop.
Limites
Detecta um único loop com divisão por 2 usando left/right/mid.
Complexidade
Reconhece o padrão de busca binária e classifica como O(log n).
Limitações e decisões de design
O objetivo é ser rápido e útil para estudo, não provar matematicamente a complexidade.
Algoritmos comuns são detectados por convenções de nomenclatura e padrões estruturais. Implementações não padronizadas podem não ser reconhecidas corretamente.
Os parsers usam regex e correspondência de palavras-chave em vez de parsers completos de linguagem. Isso torna o sistema portável e rápido, mas pode perder casos extremos em código complexo.
Quer aprender mais?
Agora que você entende como o analisador funciona, experimente com seus próprios códigos ou aprofunde-se nas referências de tipos de complexidade.