Complexidade e Big-O

Quanto o seu código cresce — e como o DataForge mede isso sem rodar nada.

Um algoritmo que funciona com dez itens pode não terminar com um milhão. Big-O é a linguagem para falar disso antes de descobrir na produção.

O DataForge analisa complexidade de dentro: dataforge big-o lê a árvore do seu programa e diz a classe de cada ação — e o motivo. Não é uma calculadora à parte; é o mesmo compilador que roda o código.

action comuns(xs, ys):
    saida := []
    cycle x in xs:
        given x in ys:
            saida.append(x)
    yield saida

$ dataforge big-o exemplo.df -v

  ▲ comuns                     O(n^2)      tempo   O(n) espaco
      · 'cycle … in 'xs'' na linha 3 anda uma vez por item
      · 'in' na linha 4 percorre a colecao (use um vault para O(1))
      ⚠ O(n^2): dobrar a entrada quadruplica o tempo.
        se um dos lacos so procura um item, um vault faz isso em O(1)

As curvas#

A tabela diz que O(n²) é pior que O(n log n). O gráfico mostra quanto — e é isso que decide projeto. Clique nas classes para comparar; arraste para mudar o tamanho da entrada.

O que cada classe custa#

Os números não são decorativos. É a diferença entre "isso é lento" e "isso não termina antes do almoço":

Um O(n²) com um milhão de itens são 10¹² operações — cerca de onze dias a um milhão de operações por segundo. O mesmo problema em O(n log n) são 20 milhões: vinte segundos.

Linear contra logarítmica, vendo#

A busca linear olha caixa por caixa. A binária descarta metade a cada passo. Com 32 itens a diferença já aparece; com um milhão, é 1.000.000 contra 20.

O que Big-O não diz#

Três coisas que a notação deliberadamente ignora, e que às vezes decidem a escolha:

• A constante. O(n) com constante 1000 perde de O(n²) com constante 1 até n=1000. Big-O é sobre crescimento, não sobre velocidade.
• A memória. Um algoritmo O(n log n) que aloca uma cópia pode perder para um O(n²) que trabalha no lugar, quando a memória é o gargalo.
• O caso médio. O(n²) é o pior caso do quicksort; o médio é O(n log n), e é ele que se observa. Ver melhor, médio e pior caso.

Por onde seguir#