O que é a notação Big O?

A notação Big O (Big O) é uma notação matemática usada para descrever o comportamento assintótico de uma função e seu limite superior. No contexto do desenvolvimento de software, ela é aplicada para avaliar o desempenho dos algoritmos em termos de consumo de tempo (complexidade temporal) e memória (complexidade espacial) à medida que o tamanho dos dados de entrada aumenta. Ela descreve o cenário de pior caso de execução.

As classes de complexidade de tempo mais comuns:

• O(1): Tempo constante. O tempo de execução não depende do tamanho dos dados de entrada.
• O(log n): Tempo logarítmico. O tempo de execução cresce lentamente com o aumento do tamanho dos dados de entrada (por exemplo, busca binária).
• O(n): Tempo linear. O tempo de execução é proporcional ao tamanho dos dados de entrada (por exemplo, busca linear).
• O(n log n): Tempo linear-logarítmico. Comum em algoritmos de ordenação eficientes (por exemplo, ordenação rápida, ordenação por fusão).
• O(n^2): Tempo quadrático. O tempo de execução cresce proporcional ao quadrado do tamanho dos dados de entrada (por exemplo, ordenação por bolha, ordenação por seleção).
• O(2^n): Tempo exponencial. O tempo de execução cresce muito rapidamente com o aumento do tamanho dos dados de entrada. Comum em problemas de busca exaustiva.

Exemplos de código e sua complexidade de tempo:

// O(1)
int primeiroElemento = array[0];

// O(n)
for (int i = 0; i < array.length; i++) {
    // alguma operação
}

// O(n^2)
for (int i = 0; i < array.length; i++) {
    for (int j = 0; j < array.length; j++) {
        // alguma operação
    }
}

A notação Big O foca no termo dominante na expressão e ignora as constantes e termos menos relevantes, pois em entradas grandes, sua contribuição torna-se insignificante. Por exemplo, um algoritmo com complexidade O(2n^2 + 5n + 10) é considerado O(n^2).

Compreender o Big O é importante para escolher os algoritmos e estruturas de dados mais eficientes ao desenvolver.