Para que serve a notação O, e o que ela esconde

Um comentário de code review diz "isso é O(n ao quadrado), reescreve". O loop percorre os cursos em que uma pessoa está matriculada. O catálogo inteiro tem algumas centenas de cursos, e quem estuda costuma estar matriculado num punhado deles. A reescrita economizaria microssegundos e custaria uma tarde de quem revisa.

Um segundo comentário, em outro pull request, nunca foi escrito. Aquele loop chama include? num array montado com todas as lições do catálogo, uma vez por linha de um relatório. Ninguém apontou porque o código se lê bem.

A análise de complexidade se paga quando diz qual dos dois importa. É ferramenta de decisão, não medalha.

O que a notação afirma

A notação O nomeia o formato de uma curva de crescimento. Ela responde a uma pergunta e se recusa a responder qualquer outra: quando a entrada fica dez vezes maior, o que acontece com o trabalho?

O(1) diz que nada acontece. O(n) diz que o trabalho fica dez vezes maior. O(n ao quadrado) diz que fica cem vezes maior. O(log n) diz que ele cresce uma fatia constante cada vez que você dobra a entrada.

Esse é todo o conteúdo da afirmação. É uma frase sobre um limite quando n cresce sem parar, e por isso ela se cala de propósito sobre todo caso finito que você vai rodar na vida.

As três coisas que ela joga fora

A notação descarta constantes. Um algoritmo que faz 4000 unidades de trabalho por elemento e um que faz 3 são ambos O(n). Nos seus dados, um leva um segundo e o outro leva um milissegundo.

Ela descarta termos de ordem menor. n ao quadrado + 500n é O(n ao quadrado), e para qualquer n abaixo de 500 o termo descartado faz a maior parte do trabalho.

E ela descarta a máquina. Uma varredura sequencial de um array que cabe no cache L1 e uma varredura sequencial de uma tabela em disco são a mesma curva e mundos diferentes.

Então a leitura honesta de "isso é O(n log n)" é: se n continuar crescendo, esse é o formato que vai seguir. É uma previsão sobre o futuro dos seus dados, e não uma medição de hoje.

A pergunta que vem antes

Antes da curva vem uma pergunta: o que é n aqui?

Quem diz "esse sort é O(n log n)" sem saber dizer se n é 40 ou 40 milhões produziu uma frase verdadeira e sem informação nenhuma. A curva só vira decisão quando está presa a um número.

Esta aplicação é um exemplo útil, porque os números dela são pequenos. Aqui estão as ordens de grandeza, que qualquer pessoa vê no catálogo:

Nesses tamanhos quase nada aqui merece um argumento assintótico. Uma varredura linear sobre algumas centenas de itens em Ruby leva uma fração de milissegundo. Dizer isso em voz alta ajuda mais o time do que fingir que os números são maiores. Isso leva a atenção para os dois ou três lugares onde n cresce mesmo.

Onde deixa de ser numerologia

A complexidade vira ferramenta de sênior em três situações, e você vai reconhecer as três.

A primeira é uma curva que bate numa parede. Qualquer coisa quadrática numa requisição de usuário vai bem até deixar de ir, e a mudança é abrupta: uma página que levava 80ms com 300 linhas leva 8 segundos com 3000. O crescimento linear se degrada aos poucos; o quadrático cai de um penhasco.

A segunda é uma curva que você não enxerga. Uma query por registro dentro de um loop parece uma linha de Ruby. O custo não está no Ruby.

A terceira é uma decisão entre duas implementações que funcionam. As duas estão corretas, as duas estão em produção, e a única diferença é qual delas ganha nos seus dados. Essa é a questão do limiar, e é o coração deste curso.

O que este curso cobre

A lição 2 percorre as curvas que uma pessoa que trabalha com Rails encontra, cada uma presa a um par concreto. Ela compara uma query por registro com uma query só, busca por índice com varredura sequencial, ordenar em Ruby com ordenar no banco e carregar todas as linhas com processar em lotes.

A lição 3 é o quadrático acidental mais comum em código Rails: include? num array dentro de um loop. Ela mede o custo em vez de afirmá-lo e mostra o que o Set faz com ele no Ruby atual.

A lição 4 é complexidade de espaço, que juniores ignoram e que acorda seniores de madrugada. A curva de memória costuma doer antes da curva de tempo.

A lição 5 é custo amortizado, caso médio e pior caso. Ela cobre por que um acesso a Hash é "O(1)" com ressalvas, e onde o pior caso morde na prática.

A lição 6 é a questão do limiar. Duas implementações têm curvas e constantes diferentes, e elas se cruzam num ponto que você consegue calcular. Ela traz o desafio de código.

A lição 7 é sobre quando a análise vale a pena.

Antes da lição 2

Abra o endpoint mais usado que você mantém e encontre os loops. Para cada um, anote o que é n e o que ele era um ano atrás. Deixe a curva para depois. Anote só o número e a direção dele.