Entendendo Big O Notation
Recentemente eu estava praticando alguns exercícios no site LeetCode e um detalhe nas instruções chamou minha atenção: "A solução deve ter complexidade de tempo O(1), O(n), O(log n) para ser considerada correta".
No dia-a-dia nos preocupamos apenas em resolver um problema mas raramente pensamos na complexidade e performance do algoritmo.
Um loop que fazemos num array leva milisegundos para ser executado, isso é quase imperceptível. Mas conforme criamos grandes aplicações, com grande quantidade de dados, isso pode se tornar um gargalo de performance.
Pra isso usamos a Big O Notation para medir a performance de um algoritmo.
A Notação Big O é, essencialmente, a ferramenta que usamos para medir a performance de um algoritmo. Ela não conta o tempo em segundos, mas sim o crescimento do número de operações à medida que o volume de dados de entrada (n) aumenta.
Em suma: ela responde à pergunta: "O quanto meu código vai ficar lento se a minha base de usuários ou de dados crescer 1000x?".
O melhor é manter nosso código com a complexidade O(1) (Busca por index), O(log n) (Busca binária) ou O(n) (Busca linear), nessa ordem. Vamos entender cada uma delas.
1. Notação O(1) - Complexidade Constante
Não importa se o seu array tem 1 item ou 1 milhão de itens, o tempo de execução será rigorosamente o mesmo, O(1).
Um exemplo clássico é acessar um elemento diretamente pelo seu índice em um array (O(1)) ou buscar uma chave em um objeto (O(1)).
function buscarPrimeiroElemento(arr) {
return arr[0]; // Sempre faz apenas 1 operação
}
const frutas = ['maçã', 'banana', 'laranja', 'morango'];
console.log(buscarPrimeiroElemento(fritas)); // 'maçã'
2. Notação O(log n) - Complexidade Logarítmica
A complexidade logarítmica parece assustadora pelo nome, mas a lógica é linda: a cada passo que o algoritmo dá, ele divide o problema pela metade. O exemplo perfeito aqui é a Busca Binária (Binary Search).
Imagine que você está procurando uma palavra em um dicionário físico; você não lê página por página, você abre no meio e descarta a metade que não interessa. O mesmo vale para a busca binária.
Nota importante: para a busca binária funcionar, a lista obrigatoriamente precisa estar ordenada.
function buscaBinaria(arr, alvo) {
let inicio = 0;
let fim = arr.length - 1;
while (inicio <= fim) {
let meio = Math.floor((inicio + fim) / 2);
if (arr[meio] === alvo) return meio; // Achou!
if (arr[meio] < alvo) {
inicio = meio + 1; // Descarta a metade esquerda
} else {
fim = meio - 1; // Descarta a metade direita
}
}
return -1; // Não encontrou
}
const numerosOrdenados = [10, 20, 30, 40, 50, 60, 70, 80];
console.log(buscaBinaria(numerosOrdenados, 60)); // Índice 5
A cada loop ele chega mais perto do alvo, o que faz o algoritmo percorrer menos itens. Por isso a complexidade é O(log n).
3. Notação O(n) - Complexidade Linear
Aqui, o tempo de execução cresce na mesma proporção que os dados de entrada. Se você tem 10 itens, faz 10 operações. Se tem 10.000 itens, faz 10.000 operações.
O caso mais comum do nosso dia a dia é o bom e velho loop (for, forEach, map, find) varrendo um array para buscar ou transformar dados.
function contemItem(arr, alvo) {
return arr.find(item => item === alvo);
}
const usuarios = ['Sérgio', 'Ana', 'Beatriz'];
console.log(contemItem(usuarios, 'Ana')); // Executa proporcionalmente ao tamanho do array
4. Notação O(n log n) - Complexidade Linear-Logarítmica
Essa complexidade geralmente aparece em algoritmos de ordenação eficientes, como o Merge Sort ou Quick Sort. O JavaScript usa essa abordagem por baixo dos panos no método nativo Array.prototype.sort().
A lógica consiste em dividir o array consecutivamente pela metade (log n) e, depois, passar juntando e ordenando os elementos (n).
// Exemplo conceitual usando o método nativo de ordenação do JS
function ordenarLista(arr) {
return arr.sort((a, b) => a - b); // O motor do V8 otimiza isso para O(n log n)
}
const numerosBagunçados = [5, 1, 4, 2, 8];
console.log(ordenarLista(numerosBagunçados)); // [1, 2, 4, 5, 8]
5. Notação O(n²) - Complexidade Quadrática
A complexidade quadrática acontece quando o tempo de execução cresce ao quadrado do número de elementos.
O gatilho clássico para um código virar O(n²) é ter um loop dentro de outro loop (nested loops). Para cada item do array de fora, você percorre o array de dentro inteiro novamente. Se a sua lista crescer um pouco, a sua aplicação vai engasgar.
function encontrarDuplicados(arr) {
let duplicados = [];
for (let i = 0; i < arr.length; i++) {
for (let j = i + 1; j < arr.length; j++) {
if (arr[i] === arr[j] && !duplicados.includes(arr[i])) {
duplicados.push(arr[i]);
}
}
}
return duplicados;
}
console.log(encontrarDuplicados([1, 2, 3, 2, 4, 1])); // [1, 2]
6. Notação O(2^n) - Complexidade Exponencial
No crescimento exponencial, a cada novo elemento adicionado na entrada, o esforço do algoritmo dobra. Um exemplo muito conhecido disso é a implementação recursiva ingênua para calcular a sequência de Fibonacci. Como a função chama a si mesma duas vezes para cada nível, ela gera uma árvore de chamadas gigantesca e redundante.
function fibonacciRecursivo(n) {
if (n <= 1) return n;
// Duas chamadas recursivas para cada execução. Evite isso para números grandes!
return fibonacciRecursivo(n - 1) + fibonacciRecursivo(n - 2);
}
console.log(fibonacciRecursivo(6)); // 8
Combinando complexidades
As vezes podemos ver uma função que combina duas complexidades, como O(n) + O(1).
function minhaFuncao(arr) {
arr[0]; // O(1)
return arr.map(...); // O(n)
}
Nesse caso a complexidade predominante é O(n), pois ele leva mais tempo para executar o map do que o arr[0].
Lembre-se: a complexidade de maior curva sempre será a predominante.
Soma de complexidades
Podemos ter uma função com N loops, por exemplo O(n) + O(n) + O(n). Você pode pensar que a complexidade é O(3n), mas nesse caso ignoramos a constante e consideramos apenas O(n).
function minhaFuncao(arr) {
// O(n)
for (let i = 0; i < arr.length; i++) {
console.log(arr[i]);
}
// O(n)
for (let i = 0; i < arr.length; i++) {
console.log(arr[i]);
}
// O(n)
for (let i = 0; i < arr.length; i++) {
console.log(arr[i]);
}
}
Complexidade de Tempo X Espaço
Além de medir o tempo de execução, também usamos Big O Notation para analisar a complexidade de espaço, que representa a quantidade de memória adicional que um algoritmo precisa em relação ao tamanho da entrada.
function soma(arr) {
let total = 0;
for (const num of arr) {
total += num;
}
return total;
}
Embora o tamanho do array de entrada possa crescer, o algoritmo continua utilizando apenas uma quantidade fixa de memória adicional. Por isso, sua complexidade de espaço é O(1). Já sua complexidade de tempo é O(n), pois cada elemento do array precisa ser visitado uma vez.
Conclusão
Saber Big O Notation é essencial para criar algoritmos eficientes e escaláveis em grandes aplicações e encontrar gargalos de performance que podem ser melhorados.
Muitas empresas grandes perguntam sobre Big O Notation nas entrevistas técnicas e isso pode ser um diferencial para você.
Nos próximos posts, vamos começar a destrinchar padrões de algoritmos e estruturas de dados como Two Pointers, Sliding Window e HashMaps.
Sabendo o Big O de cada um deles, você vai entender perfeitamente o motivo de escolher uma abordagem em detrimento de outra.
