Crescimento Big-O: quanto cada classe de complexidade custa de verdade
Seus dados
Dois algoritmos frente a frente
A constante é tudo o que a notação joga fora: alocações, falhas de cache, o trabalho dentro de cada passo. Dê a um dos algoritmos uma constante mais pesada e veja onde ela deixa de importar.
Esta página não lê o seu laço. Adivinhar a complexidade lendo código seria um palpite vestido de medição: um laço pode sair no meio, uma única chamada lá dentro pode esconder o custo de verdade, e recursão quase nunca se lê pelo que faz. Você escolhe a classe; o que a página calcula a partir dela é exato.
Resultados
| Onde um ultrapassa o outro, em itens | — |
| Operações de cada um, no tamanho acima | — |
Com os números com que esta página começa, o cruzamento fica em 439 itens. Quem troca pela classe melhor numa lista de duzentos deixou o programa mais lento e o código mais difícil, e a notação não avisou — porque a notação fala do que acontece no fim das contas, não do que acontece com você.
Cada classe neste tamanho
| Classe | Operações | Tempo | Multiplicado por, se a entrada dobrar |
|---|
A última coluna é a que vale encarar, porque é a coluna que ninguém carrega na cabeça. Trabalho linear dobra. Trabalho quadrático quadruplica. Trabalho exponencial é elevado ao quadrado: com mil itens já em jogo, dobrar a entrada multiplica o custo por dois elevado a mil, um número de trezentos e dois dígitos.
O fatorial é pior de um jeito que não tem nada a ver com dobrar. Acrescentar um único item multiplica o custo pela nova contagem, então o vigésimo primeiro item custa vinte e uma vezes o problema inteiro de vinte. É por isso que um caixeiro-viajante exato com vinte cidades são 2,4 milhões de milhões de milhões de passos, ou setenta e sete anos a um bilhão por segundo, enquanto as mesmas vinte cidades sob dois elevado a n terminam em um milésimo de segundo.
Isso também explica por que a distância entre as classes é sem graça nos tamanhos pequenos e brutal nos grandes. Em dez itens, n log n e n ao quadrado estão a três vezes um do outro, o que usuário nenhum notaria. Em mil itens estão a cem vezes, e em um milhão a cinquenta mil vezes. Os mesmos dois algoritmos, o mesmo código, nada mudou além da entrada.
Ou seja: a leitura honesta de uma classe de complexidade é uma promessa sobre o formato da curva, não sobre velocidade. Ela diz como o custo reage quando a entrada cresce, e não diz absolutamente nada sobre se é rápido hoje, na sua máquina, no tamanho que você de fato tem.
Uma classe de complexidade melhor quer dizer programa mais rápido?
No seu tamanho, não necessariamente. A classe descreve como o custo reage quando a entrada cresce; ela não diz nada sobre o trabalho dentro de cada passo, e é exatamente esse trabalho que a notação joga fora.
Com os números com que esta página começa, o algoritmo quadrático de constante leve ganha do n log n com constante cinquenta em toda entrada abaixo de 439 itens. Acima disso a classe melhor dispara e nunca mais devolve a liderança.
Por que esta página não lê o meu código?
Porque adivinhar a complexidade a partir do código-fonte é um palpite vestido de medição. Um laço pode sair no meio, uma chamada lá dentro pode esconder o custo de verdade, e recursão quase nunca se lê pelo que faz.
Então aqui a classe é entrada sua, não opinião da página. Tudo o que se calcula a partir dela é aritmética exata, e nada nesta página finge saber o que o seu laço faz.
O que acontece de fato quando a entrada dobra?
Trabalho linear dobra e trabalho quadrático quadruplica, o que quase todo mundo carrega na cabeça. Trabalho exponencial é elevado ao quadrado, o que quase ninguém carrega: em mil itens, dobrar a entrada multiplica o custo por dois elevado a mil.
O fatorial nem funciona assim. Acrescentar um único item multiplica o custo pela nova contagem, então o vigésimo primeiro item custa vinte e uma vezes o problema inteiro de vinte.
| Classe | Multiplicado por quando a entrada dobra, em mil itens |
|---|---|
| O(n) | 2 |
| O(n log n) | 2,2 |
| O(n²) | 4 |
| O(n³) | 8 |
| O(2ⁿ) | 1,07 x 10^301 |
Por que um caixeiro-viajante exato é impossível com vinte cidades?
Porque vinte fatorial são 2,4 milhões de milhões de milhões de passos, que a um bilhão de operações por segundo dão setenta e sete anos. Os mesmos vinte itens sob dois elevado a n levam cerca de um milésimo de segundo.
Essa é a diferença prática entre exponencial e fatorial, e é por isso que vale separar os dois em vez de arquivar ambos como impossível.
Reações
0
0 Comentários
Seja o primeiro a comentar