Quão rápido? Notação O grande

A um bilhão de passos por segundo, um método n² com um milhão de valores leva cerca de 17 minutos; um método n log n leva 0.02 segundo.

O crescimento importa mais que a contagem exata

Até agora contamos os passos com exatidão: 45 comparações, 4 trocas, 20 verificações. Contagens exatas são úteis em exemplos pequenos, mas dependem de detalhes, como se o bubble sort para antes ou como o pivô é escolhido. Quando a entrada fica grande, uma coisa domina todo o resto: como a contagem cresce à medida que n cresce. Um algoritmo cujos passos crescem como n² vai acabar perdendo para um cujos passos crescem como n log n, por mais bem ajustado que o primeiro esteja.

A notação O grande (Big O) é a forma abreviada de descrever esse crescimento. Escrever que um algoritmo é O(n²), que se lê "O grande de n ao quadrado", quer dizer que, para n grande, a contagem de passos dele é no máximo uma constante vezes n². Duas regras facilitam o uso. Descarte os fatores constantes: 3n e n/2 são ambos O(n). Fique só com o termo que cresce mais rápido: n²/2 − n/2, as comparações do selection sort, é O(n²), porque para n grande a parte n² é quase tudo. O curso 6.006 do MIT usa a mesma ideia quando compara estruturas de dados e métodos de ordenação pelo tempo de execução assintótico.

As taxas de crescimento comuns

• O(1), constante. O trabalho não depende de n: ler o primeiro valor de uma lista, ou um valor numa posição conhecida.
• O(log n), logarítmica. Cada passo corta o problema ao meio: busca binária. Um milhão de valores, cerca de 20 passos.
• O(n), linear. Cada valor é tratado uma vez: busca linear, achar o maior valor, somar uma lista.
• O(n log n). Merge sort, e quicksort em média. O melhor que a ordenação por comparação consegue.
• O(n²), quadrática. Todos os pares são examinados: bubble sort, selection sort e insertion sort no pior caso, ou dois laços um dentro do outro.
• O(2ⁿ), exponencial. O trabalho dobra a cada valor a mais: testar todos os subconjuntos de n itens, ou mover n discos na Torre de Hanói.

O que os números querem dizer em segundos

Suponha que um computador faça um bilhão (10⁹) de passos básicos por segundo, um número redondo razoável para um núcleo de processador. Veja o que cada taxa de crescimento significa para um milhão de valores. O(log n) dá cerca de 20 passos, bem menos de um microssegundo. O(n) dá um milhão de passos, um milissegundo. O(n log n) dá cerca de 20 milhões de passos, 0.02 segundo. O(n²) dá 10¹² passos, mil segundos, cerca de 17 minutos. O(2ⁿ) não pode ser concluído: 2 elevado a um milhão é um número com mais de 300 000 algarismos. É por isso que escolher o algoritmo certo costuma importar muito mais do que comprar um computador mais rápido. Uma máquina dez vezes mais rápida transforma 17 minutos em 1.7 minuto; trocar O(n²) por O(n log n) transforma isso num quinquagésimo de segundo.

Lendo a notação O grande no código

Muitas vezes dá para ler a taxa de crescimento direto na forma do código. Um único laço sobre a lista é O(n). Dois laços, um dentro do outro, ambos sobre a lista, são O(n²): para cada uma das n voltas de fora, o laço de dentro faz até n voltas. Um laço que corta um número ao meio a cada vez, como while (n > 1) n = Math.floor(n / 2), é O(log n): partindo de 1000 ele roda 9 vezes, de um milhão 19 vezes. Passos que acontecem um depois do outro se somam, e vence o termo maior: um laço O(n) seguido de um laço O(n²) é O(n²) no total.

// O(n): uma passada
let total = 0;
for (const x of list) total += x;

// O(n²): todos os pares
for (let i = 0; i < list.length; i++)
  for (let j = i + 1; j < list.length; j++)
    if (list[i] === list[j]) console.log("duplicate", list[i]);

// O(log n): cortes ao meio
let k = list.length, rounds = 0;
while (k > 1) { k = Math.floor(k / 2); rounds++; }

Melhor caso, caso médio e pior caso

Um algoritmo pode se comportar de modos muito diferentes em entradas diferentes. O insertion sort é O(n) numa lista já ordenada e O(n²) numa invertida. O quicksort é O(n log n) em média e O(n²) com pivôs ruins o tempo todo. Quando alguém cita uma única notação O grande sem dizer qual caso, em geral está falando do pior caso, porque ele é uma garantia: o algoritmo nunca vai fazer pior que isso. A notação O grande também deixa coisas de fora. Ela ignora os fatores constantes, então, em entradas pequenas, um método O(n²) com passos muito simples pode vencer um O(n log n). É por isso que muitas rotinas de ordenação de verdade passam para o insertion sort nos pedaços curtos da lista.