Entendendo Big O de forma mastigada

Como a notação Big O finalmente fez sentido depois de Entendendo Algoritmos — O(1), O(n) e O(log n) explicados de forma bem mastigada.

Mesmo depois de já formado na faculdade e trabalhando como desenvolvedor, eu não fazia a mínima ideia do que era O(1), O(n), etc. Honestamente, já tinha lido sobre em alguns lugares e me parecia um assunto complicado e chato.

Recentemente, comprei o livro Entendendo Algoritmos e nele tudo finalmente ficou claro. E para quem ainda não sabe ou teve a mesma dor que eu, vou explicar de forma bem mastigada.

O que é um algoritmo?

Devemos ir bem do começo para que tudo fique claro. Um algoritmo nada mais é do que uma sequência de passos para resolver um problema ou executar uma tarefa. Na programação, praticamente tudo que escrevemos é um algoritmo.

O que é a Notação Big O?

A própria nomenclatura facilita o entendimento. A Notação Big O é uma forma de medir a eficiência de um algoritmo. Ela nos ajuda a entender como o tempo de execução ou o consumo de memória crescem à medida que a quantidade de dados aumenta.

O detalhe mais importante é que ela não mede segundos ou minutos. Quando dizemos que um algoritmo é O(n), não estamos dizendo que ele leva exatamente 1 segundo, 2 segundos ou 10 segundos para executar. Estamos descrevendo como ele se comporta conforme a entrada cresce.

O(1) — Tempo constante

Um algoritmo O(1) executa sempre a mesma quantidade de operações, independentemente do tamanho da entrada.

Exemplo:

const lista = [10, 20, 30, 40, 50];

// Acessar um índice específico é O(1)
const valor = lista[2];
console.log(valor); // 30

Não importa se a lista possui 10 elementos ou 10 milhões. Acessar uma posição específica de um array leva praticamente o mesmo tempo.

O(n) — Tempo linear

Um algoritmo O(n) precisa percorrer todos os elementos da entrada.

Por exemplo, encontrar o maior número de um array:

function maiorNumero(lista) {
  let maior = lista[0];

  for (const numero of lista) {
    if (numero > maior) {
      maior = numero;
    }
  }

  return maior;
}

Se o array tiver 10 elementos, faremos 10 verificações. Se tiver 1000 elementos, faremos 1000 verificações.

O(log n) — Tempo logarítmico

O O(log n) aparece quando conseguimos descartar uma grande quantidade de elementos a cada operação. O exemplo clássico é a busca binária.

Imagine que você tem uma lista ordenada com 100 números e quer encontrar o número 67.

Ao invés de verificar 1 por 1, você olha para o elemento do meio:

- Se o número procurado for maior, descarta toda a metade esquerda. - Se for menor, descarta toda a metade direita.

A cada passo você elimina metade dos elementos restantes.

`100 → 50 → 25 → ...`

Quanto mais os dados crescem, mais lentamente o número de operações aumenta.

À primeira vista parece algo complicado, mas com algumas repetições se torna algo bem óbvio.