Notação Big O

O que é a notação Big O

A notação Big O descreve como o custo de um algoritmo cresce conforme o input cresce. Ela não vai te dizer que uma função leva 3 milissegundos. Ela diz o que acontece com essa função quando o input passa de mil itens para um milhão.

Ou seja, Big O fala de escalabilidade, não de performance bruta. Duas funções podem rodar igualmente rápido na sua máquina com os dados de teste que você tem hoje. Quando os dados reais ficarem cem vezes maiores, uma delas pode continuar tranquila e a outra virar o motivo da sua página demorar dez segundos para carregar. O Big O serve para você perceber a diferença antes disso acontecer.

A notação é a letra O seguida de uma função de n, onde n é o tamanho do input: O(1), O(n), O(n²). Você lê O(n) como "cresce na proporção de n".

Tempo e espaço

Todo algoritmo tem dois tipos de complexidade:

• Complexidade de tempo é como o número de operações cresce com n.
• Complexidade de espaço é como a quantidade de memória extra que o algoritmo aloca cresce com n.

A palavra importante aí é extra. O input já está na memória antes do algoritmo rodar, então ele não entra na conta. O que conta é o que o algoritmo cria no caminho, como uma cópia de um slice, um map com os valores que já viu ou a call stack de uma função recursiva.

As duas são medidas separadamente e não precisam ser iguais. Uma função pode ser O(n) em tempo e O(1) em espaço ao mesmo tempo. Encontrar o maior número de um slice é um bom exemplo:

Não tem como saber qual é o maior número sem olhar todos, então o loop passa por cada elemento. Isso deixa o tempo em O(n). A memória é outra história: não importa o tamanho do slice, a função só guarda uma variável extra, best. Isso deixa o espaço em O(1).

Agora o mesmo resultado calculado de outro jeito:

A resposta está certa, mas é pior nos dois quesitos. A ordenação deixa o tempo em O(n log n), e a cópia deixa o espaço em O(n). Num slice de dez números você nem percebe. Num slice de dez milhões, a primeira versão ganha fácil.

Sempre considere o pior caso

Quando for analisar um algoritmo, seja pessimista. Procure o input que faz ele trabalhar mais e descreva esse caso.

Pense numa busca linear, que percorre um slice até achar um valor. Se o valor está na primeira posição, ela termina depois de uma comparação. Se o valor está na tail, ou nem está no slice, ela precisa comparar todos os elementos. O Big O descreve a segunda situação, então a busca linear é O(n).

O motivo é que o melhor caso não promete nada. "É rápido quando o item por acaso está no começo" depende de sorte, não do algoritmo. Já o pior caso é uma garantia: chegue o input que chegar, o algoritmo nunca vai fazer mais trabalho que aquilo. É esse o número que interessa quando você quer saber se algo vai aguentar em produção.

E input ruim é mais comum do que parece. No artigo de Binary Search Trees, dados que já chegam ordenados, que é a coisa mais normal do mundo, transformam toda operação O(log n) em O(n).

Escalabilidade, não velocidade

Um Big O melhor normalmente é o que você quer, mas ele não significa mais rápido. Você não pode dizer que um algoritmo O(n) é mais rápido que um O(n²). Dá para dizer apenas qual dos dois lida melhor com o crescimento.

Isso acontece porque o Big O deixa detalhes de fora de propósito. Imagine que o algoritmo A faz 100n operações e o algoritmo B faz n²:

Com menos de 100 elementos, o B faz menos trabalho, mesmo sendo o quadrático. Em 100 eles empatam. Depois disso o A fica na frente de vez, e com um milhão de elementos o B está fazendo dez mil vezes mais trabalho.

Isso aparece em código de verdade. O slices.Sort do Go é um algoritmo O(n log n), mas quando um pedaço do slice tem 12 elementos ou menos, ele troca para insertion sort, que é O(n²). Para inputs pequenininhos, o algoritmo mais simples tem menos overhead e termina primeiro. O Big O só descreve o que acontece conforme n continua crescendo.

Descartando constantes e termos menores

A mesma ideia dá origem às duas regras de simplificação que você vai ver em todo lugar:

• Descarte as constantes. 100n, 2n e n / 2 são todos O(n). A constante deixa a reta mais ou menos inclinada, mas ela continua sendo uma reta: dobrou o input, dobrou o trabalho.
• Fique só com o maior termo. n² + n é O(n²). Com um milhão de elementos, n² é um trilhão e n é um milhão, então o termo menor quase não faz diferença.

Pela mesma lógica, uma quantidade fixa de trabalho é O(1) mesmo quando é grande. Quinhentas operações que nunca mudam com n continuam sendo constantes.

As classes de complexidade mais comuns

A maioria dos algoritmos que você vai encontrar cai em poucas classes. Aqui estão elas no mesmo gráfico:

As próximas seções passam por uma de cada vez, da curva mais plana até a mais íngreme.

O(1): constante

Uma operação O(1) leva o mesmo tempo, ou usa a mesma memória, não importa o tamanho do input.

Ler o primeiro item de um slice é o exemplo mais simples:

O tamanho de nums não importa. A função lê uma posição e retorna. O mesmo vale para ler qualquer índice: como o artigo de Arrays explica, o endereço de nums[i] é calculado com uma multiplicação e uma soma, então nums[999999] custa o mesmo que nums[0]. Verificar se um número é par (n%2 == 0) e fazer push numa stack também são constantes.

O(log n): logarítmica

A versão curta: o input pode crescer muito enquanto o custo cresce bem pouco.

A versão mais precisa: quando o input cresce exponencialmente, o custo cresce linearmente. Cada vez que você dobra n, um algoritmo logarítmico precisa de um passo a mais. Ir de mil elementos para um milhão, que é mil vezes mais dados, adiciona uns dez passos.

Para entender o porquê, vale lembrar o que é um logaritmo. Ele é o inverso de uma potência. 2³ = 8 quer dizer "multiplique 2 por ele mesmo 3 vezes e você tem 8". log₂ 8 = 3 faz a pergunta ao contrário: "quantas vezes eu multiplico 2 para chegar em 8?"

Em programação tem um jeito mais útil de ler isso: log₂ n é quantas vezes você consegue dividir n pela metade até chegar em 1. Divida 8 pela metade e você tem 4, depois 2, depois 1. Foram três divisões, então log₂ 8 = 3. Repare como esse número cresce devagar:

Mesmo com um bilhão de elementos, trinta divisões pela metade bastam para chegar em um.

A gente usa base 2 em programação porque muitos algoritmos funcionam dividindo as coisas em duas: um intervalo ordenado, uma tree em subtree esquerda e direita, um problema em duas metades. No Big O, porém, a base não importa. Trocar a base de um logaritmo só multiplica ele por uma constante (log₁₀ n é log₂ n dividido por mais ou menos 3,32), e constantes são descartadas. Por isso se escreve só O(log n).

O exemplo clássico é a binary search. Num slice ordenado, olhe o elemento do meio. Se o alvo for maior, ignore a metade esquerda. Se for menor, ignore a metade direita. Cada comparação joga fora metade do que sobrou.

Mesmo no pior caso, quando o valor não está lá, o loop roda mais ou menos log₂ n vezes. Ele só guarda low, high e mid, então o espaço é O(1).

Dá para comparar com a busca linear aqui embaixo. Clique num número para buscar ele com os dois algoritmos ao mesmo tempo. Teste o último elemento, que é o pior caso da busca linear, e depois um valor que não está no array. Em seguida, troque o tamanho: a busca linear precisa do dobro de comparações cada vez que o array dobra, enquanto a binary search precisa de só uma a mais.

Você provavelmente já usou essa estratégia sem escrever código nenhum. No jogo de "adivinhe o número entre 1 e 100", chutar sempre o meio acha qualquer número em no máximo 7 tentativas, já que 2⁷ = 128. Procurar uma palavra num dicionário de papel funciona igual: você abre mais ou menos no meio e vai descartando metade. Até contar os dígitos de um número é logarítmico. Um número com d dígitos fica perto de 10ᵈ, então ele tem uns log₁₀ n dígitos.

O(n): linear

Num algoritmo O(n), o custo cresce no mesmo ritmo do input. O dobro de dados, o dobro de trabalho.

Tudo que precisa visitar todos os elementos é linear: somar um slice, imprimir ele ou buscar nele quando ele não está ordenado.

Se target for o primeiro elemento, a função retorna na hora. Como estamos sendo pessimistas, porém, consideramos que o alvo está na tail ou não existe, o que dá n comparações. É exatamente a primeira linha do playground lá em cima.

Em espaço, linear significa alocar memória na proporção do input. Criar um slice novo com uma cópia transformada de cada elemento é o caso típico:

Essa função é O(n) em tempo e O(n) em espaço: ela passa pelo input uma vez e cria um elemento novo para cada elemento que lê.

O(n log n): linearítmica

O(n log n) normalmente vem de divide and conquer: divida o problema ao meio, resolva cada metade de forma recursiva e depois junte os resultados. Os algoritmos de ordenação eficientes de uso geral ficam aqui.

O merge sort é o mais fácil de acompanhar. Para ordenar um slice, divida ele em duas metades, ordene cada metade do mesmo jeito e depois faça o merge das duas metades ordenadas numa só:

O n log n é a multiplicação de duas coisas separadas, e fica mais fácil entender uma de cada vez. Aperte Ordenar para ver o merge sort dividir 8 valores até sobrar um elemento em cada parte e depois fazer o merge de volta. Conte as linhas na descida, e os elementos de cada linha de merge na subida.

• São O(log n) níveis. Cada nível divide os slices ao meio, e 8 só pode ser dividido ao meio três vezes antes de sobrarem elementos sozinhos, então são log₂ 8 = 3 níveis.
• Cada nível custa O(n). Na volta, o merge passa por cada elemento uma vez por nível. Os slices ficam menores, mas são mais numerosos, então cada nível continua lidando com todos os n elementos.

log n níveis com n de trabalho em cada um dá O(n log n). O merge sort ainda precisa de O(n) de espaço extra para os slices do merge.

O quicksort usa a mesma ideia de divide and conquer, mas divide o slice em torno de um elemento escolhido, o pivot, em vez do meio. Quando os pivots dividem os dados de forma equilibrada, ele roda em O(n log n), e na prática costuma ser mais rápido que o merge sort. Quando o pivot é sempre o menor elemento, o que acontece com uma escolha ingênua de pivot em dados que já estão ordenados, as "metades" ficam com n − 1 elementos e 0 elementos. A recursão desce n níveis e o quicksort vira O(n²). É a regra do pior caso de novo, e é por isso que o slices.Sort do Go usa pattern-defeating quicksort: ele percebe quando as divisões estão ficando ruins e troca para heapsort, que é O(n log n) independente do input.

O(n²): quadrática

O(n²) é basicamente um loop dentro de um loop, os dois percorrendo o input. Para cada um dos n elementos, você faz n unidades de trabalho.

O bubble sort é o exemplo de sempre. Ele percorre o slice comparando vizinhos e troca os dois quando estão na ordem errada. Depois de cada passada, o maior elemento que sobrou "borbulhou" até o final. Ele repete isso até tudo estar ordenado.

O loop de dentro fica menor a cada passada, então a conta exata é (n−1) + (n−2) + … + 1 = n(n−1)/2 comparações. Expandindo, dá n²/2 − n/2. Descarte a constante e o termo menor e sobra O(n²). O espaço é O(1), porque ele ordena o próprio slice.

Rode abaixo e fique de olho no contador. Embaralhado ou invertido, ele sempre faz o mesmo número de comparações; o input só muda quantas trocas acontecem. Depois vá de 6 para 12 elementos: o dobro de dados, umas quatro vezes mais comparações.

Algoritmos quadráticos funcionam bem com inputs pequenos e ficam ruins bem rápido. Mil elementos são um milhão de comparações, e um milhão de elementos são um trilhão. Quando algo era rápido nos testes e caiu em produção, dois loops aninhados sobre os mesmos dados são um bom primeiro suspeito.

As curiosidades acadêmicas

As classes acima cobrem a maior parte do código do dia a dia. Algumas outras aparecem menos, mas vale conhecer, umas porque são surpreendentemente boas e outras porque são péssimas.

O(√n): raiz quadrada

O(√n) fica entre a logarítmica e a linear. O exemplo mais conhecido é verificar se um número é primo usando divisão por tentativa:

Divisores vêm em pares. Se n = a × b, então a ou b é no máximo √n. Então, se nada até √n divide n, nada acima vai dividir também, e o loop pode parar ali. Para um número na casa de um trilhão, são um milhão de iterações em vez de um trilhão.

Escolha um número e verifique. O 91 e o 221 param assim que encontram um divisor, enquanto os primos precisam ir até √n. Com 9973, compare as 98 divisões que ele precisa com as quase dez mil que um loop ingênuo faria.

Repare que aqui n é o próprio número, não o tamanho de uma coleção. O Big O sempre mede o crescimento em relação ao tamanho do input, e às vezes esse tamanho é um comprimento e às vezes é um valor.

O(2ⁿ): exponencial

Um algoritmo O(2ⁿ) dobra o trabalho cada vez que o input cresce em um. Isso costuma vir de uma função recursiva que chama ela mesma duas vezes e não guarda nenhum resultado, como este Fibonacci ingênuo:

Cada chamada faz mais duas chamadas, e os mesmos valores são recalculados várias e várias vezes. fib(50) acaba chamando fib(2) bilhões de vezes. Listar todos os subconjuntos de um conjunto também é exponencial: cada elemento está dentro ou fora, então n elementos têm 2ⁿ subconjuntos.

Rode o fib(5) abaixo e acompanhe as chamadas na ordem em que elas acontecem. Cada nó azul é uma chamada para um valor que já foi calculado em algum lugar à esquerda dele. Depois troque para fib(4) e compare: 9 chamadas contra 15, com um input só um menor.

Essa função também lembra que recursão usa memória. Em qualquer momento podem existir até n chamadas esperando na call stack, então o espaço é O(n) mesmo a função nunca criando um slice.

O(n!): fatorial

Lá no fim fica a O(n!), que aparece quando um algoritmo testa todas as ordens possíveis do input. Gerar todas as permutações é o caso direto:

São n escolhas para a primeira posição, n − 1 para a segunda, e assim por diante, o que dá n × (n−1) × … × 1 = n! resultados. Resolver o problema do caixeiro-viajante por força bruta (testar todas as rotas e ficar com a mais curta) tem o mesmo formato. Com 20 cidades são uns 2,4 quintilhões de rotas. Conferindo um bilhão de rotas por segundo, você terminaria em uns 77 anos, ou seja, o caixeiro se aposenta antes da viagem ficar pronta.

Gere as ordens de algumas letras abaixo. Passar de 4 para 5 letras leva você de 24 para 120 resultados, porque cada letra nova pode ir na frente de cada ordem que você já tinha.

Arraste o slider abaixo para ver todas as classes lado a lado. Teste n = 30 e veja a exponencial e a fatorial disparando, depois vá até um milhão e veja o que acontece com a quadrática.

Algoritmos exponenciais e fatoriais só funcionam com inputs bem pequenos. Quando um problema parece precisar de um, o trabalho de verdade normalmente é achar um jeito mais esperto de formular o problema, ou aceitar uma resposta aproximada.

Resumo

• O Big O descreve como o custo cresce com o input. Um algoritmo O(n²) pode ganhar de um O(n) com inputs pequenos, e o Big O diz qual ganha conforme n cresce.
• Analise o pior caso, porque ele é o único que é garantido.
• Tempo e espaço são medidos separadamente. Achar o máximo é O(n) em tempo e O(1) em espaço.
• Descarte constantes e termos menores: 3n² + 5n + 100 é O(n²).
• Logarítmico significa dividir ao meio. Dobrar o input adiciona um passo, e a base do log não importa.
• n log n normalmente significa divide and conquer: log n níveis com O(n) de trabalho em cada.