Big O sem matemática: porque é que ficou lento

Não é para passar em entrevistas. É para responder à pergunta que aparece sempre: funcionava bem com cem registos, porque é que com dez mil demora meio minuto?

1. As quatro que aparecem mesmo

• O(1) — o tempo não depende do tamanho. Ir buscar a um Map, ler array[5].

• O(n) — percorre tudo uma vez. Um filter, um includes.

• O(n log n) — ordenar. É o melhor que há para ordenação por comparação.

• O(n²) — um ciclo dentro de outro. É aqui que mora o problema.

2. O ciclo dentro do ciclo, disfarçado

// Parece um ciclo só. São dois.
const comAutor = artigos.map((artigo) => ({
  ...artigo,
  autor: autores.find((a) => a.id === artigo.autorId),
}));

O find percorre a lista dos autores por cada artigo. Com 100 artigos e 100 autores são 10 000 comparações; com 10 000 de cada, são 100 milhões. Multiplicar por 100 as duas listas multiplicou o trabalho por dez mil.

3. A correção, quase sempre a mesma

// Um Map custa uma passagem, e depois cada procura é imediata
const porId = new Map(autores.map((autor) => [autor.id, autor]));

const comAutor = artigos.map((artigo) => ({
  ...artigo,
  autor: porId.get(artigo.autorId),
}));

Passou de O(n²) para O(n). Com dez mil de cada lado, de 100 milhões de comparações para vinte mil operações.

O mesmo vale para o includes dentro de um ciclo — troca-se a lista por um Set:

const jaVistos = new Set(vistos); // em vez de vistos.includes(...)

const novos = candidatos.filter((c) => !jaVistos.has(c.id));

4. Duas notas de bom senso

• Com listas pequenas, não interessa. Num array de vinte elementos, o find é mais legível e igualmente rápido. A pergunta a fazer é: isto pode crescer?

• A constante existe. Um O(n) que faça uma chamada à base de dados por elemento é muito pior do que um O(n²) sobre números em memória. É o mesmo problema do N+1: o que conta é o que está dentro do ciclo, não só quantas vezes ele corre.