Ao programar, nem sempre pensamos na eficiência do nosso código. Mas quando lidamos com grandes volumes de dados, escolher um algoritmo eficiente pode toda a diferença. Uma forma de medir o desempenho de um algoritmo em termos de tempo de execução e consumo de memória é utilizando a notação Big O.

A notação Big O descreve como o tempo de execução de um algoritmo cresce à medida que a entrada aumenta. 

Neste artigo vamos ver algumas das complexidades de código mais comuns. Nos exemplos vamos utilizar JavaScript

O(1) – Tempo Constante

Independente do tamanho da entrada, o tempo de execução do algoritmo permanece o mesmo.

function acessarPrimeiroElemento(array) {

  return array[0]; 

}

console.log(acessarPrimeiroElemento([10, 20, 30])); // 10

No exemplo que vimos não importa se a lista tem 10 ou 10.000 elementos, o tempo de execução é constante.

O(n) – Tempo Linear

O tempo de execução cresce proporcionalmente ao tamanho da entrada.

function imprimirElementos(array) {

  for (let item of array) {

    console.log(item);

  }

}

imprimirElementos([1, 2, 3, 4, 5]); 

Se o array tiver 5 elementos, o loop executará 5 vezes, caso ele tenha 1 milhão de lementos, ele será executado 1 milhão de vezes.

O(n²) – Tempo Quadrático

O tempo de execução aumenta exponencialmente, tornando o algoritmo lento para grandes entradas.

function paresDoArray(array) {

  for (let i = 0; i < array.length; i++) {

    for (let j = 0; j < array.length; j++) {

      console.log(array[i], array[j]);

    }

  }

}

paresDoArray([1, 2, 3]); 

Com um array de tamanho n, o loop aninhado executa n * n vezes, tornando-se rapidamente ineficiente.

O(log n) – Tempo Logarítmico

Esse tipo de complexidade aparece em algoritmos que reduzem o problema pela metade a cada iteração, um exemplo de algoritmo deste tipo é a busca binária.

function buscaBinaria(array, alvo) {

  let inicio = 0;

  let fim = array.length - 1;

  while (inicio <= fim) {

    let meio = Math.floor((inicio + fim) / 2);

    if (array[meio] === alvo) return meio;

    if (array[meio] < alvo) inicio = meio + 1;

    else fim = meio - 1;

  }

  return -1;

}

console.log(buscaBinaria([1, 3, 5, 7, 9, 11], 7)); // 3

Neste código o  tamanho da entrada é reduzido pela metade a cada iteração, tornando o algoritmo muito eficiente para buscas em grandes listas ordenadas.

Agora que vimos alguns exemplos, vamos dar uma olhada em alguns casos reais. Qual seria a complexidade de tempo de um algoritmo que percorre todos os elementos de uma lista? E se a lista estiver ordenada?

A complexidade de tempo de um algoritmo que percorre todos os elementos de uma lista uma única vez é O(n), pois o tempo de execução cresce proporcionalmente ao número de elementos na lista.

Se o algoritmo apenas percorre a lista (por exemplo, imprimindo ou somando os elementos), a complexidade permanece O(n), pois ele ainda precisa visitar cada elemento uma única vez, independentemente da ordenação.

No entanto, se o objetivo do algoritmo for buscar um elemento na lista ordenada, podemos usar busca binária, que tem complexidade O(log n), tornando a busca mais eficiente do que uma busca linear O(n).

function buscaLinear(array, alvo) {

  for (let i = 0; i < array.length; i++) {

    if (array[i] === alvo) return i;

  }

  return -1;

}

console.log(buscaLinear([1, 3, 5, 7, 9, 11], 7)); // 3

Exemplo de busca binária (O(log n)) em lista ordenada:

function buscaBinaria(array, alvo) {

  let inicio = 0;

  let fim = array.length - 1;

  while (inicio <= fim) {

    let meio = Math.floor((inicio + fim) / 2);

    if (array[meio] === alvo) return meio;

    if (array[meio] < alvo) inicio = meio + 1;

    else fim = meio - 1;

  }

  return -1;

}

console.log(buscaBinaria([1, 3, 5, 7, 9, 11], 7)); // 3

Encerramento

Compreender a notação Big O ajuda o programador a entender a complexidade de um algoritmo e prever quanta memória ou tempo computacional ele vai requerer para ser executado. Isso ajuda a escolher os algoritmos mais eficientes, melhorando o desempenho das aplicações.