Big O Notation

Qual a forma adequada de medir a eficiência de um algoritmo?

Se te pedem para comparar duas soluções para um problema, o que você faz? Bom pensando um pouco sobre isso sabemos que primeiro precisamos de alguma forma de medir ambas as soluções e para medir algo precisamos de critérios.

Bom, podemos medir de algumas formas. São elas:

Coletar tempo de execução: medir o tempo que cada solução leva para resolver o problema.
Contar instruções: contar quantas instruções cada solução faz para resolver o problema.

Essas são formas viáveis, porém possuem problemas.

Contar o tempo de execução é uma forma de medir a eficiência de um algoritmo, porém ela depende de fatores externos, como a máquina que está rodando o algoritmo, o sistema operacional, etc.

Contar quantas instruções são executadas é uma forma mais precisa, porém ela depende da linguagem de programação que está sendo utilizada. Além disso, compiladores podem otimizar o código, fazendo com que instruções sejam executadas de forma diferente.

Com o objetivo de padronizar a forma de medir a eficiência de um algoritmo, foi criada a notação Big O. A notação Big O é uma forma de descrever o comportamento de um algoritmo em termos de tempo de execução ou espaço de memória.

Isso vem da matemática, de notação assintótica. Assintótico é um termo que vem da matemática e significa que algo é válido para valores muito grandes.

Big O Notation

A notação Big O é uma forma de descrever o comportamento de um algoritmo em termos de tempo de execução ou espaço de memória.

A notação Big O descreve o pior caso de um algoritmo. Isso significa que ela descreve o comportamento do algoritmo para o pior cenário possível.

Por exemplo, se temos um algoritmo que ordena um array, o pior caso é quando o array está ordenado de forma decrescente. O melhor caso é quando o array já está ordenado.

Como usar a notação Big O

Em Big O estamos interessados em quantas operações são feitas em relação ao tamanho da entrada.

Tomemos como exemplo esse algoritmo que busca um valor em um array:

function search(arr, value) {
    for (let i = 0; i < arr.length; i++) { // n operações
        if (arr[i] === value) { // 1 operação
            return i; // 1 operação
        }
    }

    return -1;
}

// O(n) * O(1) = O(n)

Agora tomemos o mesmo algoritmo de busca, porém o array está ordenado e a busca é feita de forma binária:

function binary_search(arr, value) {
  let count = 0;
  let start = 0; // 1 operação
  let end = arr.length - 1; // 1 operação

  while (start < end) { // log(n) operações
    count++;
    let middle = Math.floor((start + end) / 2); // 1 operação

    if (arr[middle] === value) { // 1 operação
      return middle; // 1 operação
    } else if (arr[middle] < value) { // 1 operação
      start = middle + 1; // 1 operação
    } else { // 1 operação
      end = middle - 1; // 1 operação
    }
  }

  console.log(`${count} operações realizadas para encontrar o valor ${value}`);

  if (arr[start] === value) return start; // 1 operação

  return -1; // 1 operação
}

const makeArray = (from, to) => {
  let arr = [];
  for (let i = from; i <= to; i++) {
    arr.push(i);
  }
  return arr;
};

for (let i = 1; i <= 16; i++) {
  console.log(`Array de tamanho ${i}`);
  binary_search(makeArray(1, i), 10000);

  console.log('\n')
}

Em uma busca binária pode ser mais difícil de ver quantas operações são feitas, mas podemos visualizar em cada iteração. Seja um array de tamanho n, a cada iteração dividimos o array pela metade.

Seja um array de dois itens [a, b]. Digamos que procuramos c. A execução fica:

[a, b] - dividimos em [a] e [b]
a é menor que c, então vamos para a próxima iteração
[b] - dividimos em [b]
b é menor que c. Não encontramos c. O algoritmo termina.

Perceba que foram duas divisões.

Se n = 2, temos 1 operação. Se n = 3, temos 1 operação. Se n = 4, temos 2 operações. Se n = 5, temos 2 operações. Se n = 8, temos 3 operações. Se n = 16, temos 4 operações.

Assim, para um array de tamanho n, temos log(n) operações.

Tempos de execução comuns

Aqui estão alguns tempos de execução comuns:

O(1) - constante
O(log n) - logarítmico
O(n) - linear
O(n log n) - linearítmico
O(n^2) - quadrático
O(2^n) - exponencial
O(n!) - fatorial

Big O Notation

Qual a forma adequada de medir a eficiência de um algoritmo?

Big O Notation

Como usar a notação Big O

Tempos de execução comuns

O(n!) - fatorial