Entendendo a notação BIG O · luisdavitech

Você já escreveu um código que “funciona”, mas parecia ficar cada vez mais lento conforme os dados aumentavam?

Esse é o tipo de problema que a notação Big O ajuda a entender. Ela não mede tempo em segundos ou memória em megabytes, mas mostra como seu código escala à medida que o volume de dados cresce.

Neste artigo, vamos destrinchar o que é Big O, por que ela é tão importante e como identificar a complexidade do seu código de forma simples e prática.

Mas final o que é esse Big O?

Bom, Big O é uma forma de "medir" a complexidade de um código usando como base a quantidade de dados de entrada desse mesmo código, ou seja, a notação Big O consegue comparar algoritmos e dizer sua complexidade a partir da forma que ele atua. Dentre as principais formas de complexidades de algoritmos, nós temos essas três:

Complexidade constante - O(1)
Complexidade Logarítmica - O(Log N)
Complexidade Linear - O(N)

Complexidade constante - O(1)

Complexidade constante é aquele tipo de código que faz apenas uma operação com os dados independente do tamanho desses dados, no exemplo abaixo nós conseguimos ver que a função recebe uma entrada de dados(array) e ela só retorna o primeiro item desses dados, ou seja, faz apenas uma ação(pega o primeiro item)

function getFirstElement<T>(array: T[]): T | undefined {
  return array[0];
}

Complexidade Logarítmica - O(Log N)

A busca binária é um algoritmo eficiente para encontrar um elemento em um array ordenado. Ela funciona dividindo o array ao meio a cada passo: compara o elemento do meio com o alvo e descarta a metade que não pode conter o valor buscado.

Como a cada iteração o tamanho do problema é reduzido pela metade, o número de operações necessárias cresce muito mais devagar que o tamanho do array. Se o array tiver n elementos, a quantidade máxima de passos é aproximadamente log₂(n).

Ou seja, mesmo que o array fique enorme, a busca binária continua rápida, tornando sua complexidade O(log n).

function binarySearch(array: number[], target: number): number | null {
  let left = 0, right = array.length - 1;

  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    if (array[mid] === target) return mid;
    else if (array[mid] < target) left = mid + 1;
    else right = mid - 1;
  }

  return null;
}

Complexidade Linear - O(N)

Esse tipo de algoritmo tem a quantidade de operações crescendo linearmente, ou seja, se a quantidade de dados for N, a quantidade de operações será aproximadamente N, pois ele faz uma operação para cada dado recebido.

No exemplo abaixo, a função recebe um array com N dados, e ela percorre esses dados somando o dado atual com o total já somado e depois retornando, ou seja quantidade de somas feitas será igual a quantidade de itens no array.

function sumArray(array: number[]): number {
  let total = 0;
  for (const num of array) {
    total += num;
  }
  return total;
}

Me chamo Luis Davi e agradeço por ler este artigo 💚