Big O Notation

O que é Big O?

"Big O" é uma notação usada para medir o custo de um algoritmo em termos de tempo de execução ou uso de recursos como o espaço de memória, também conhecidos como complexidade.

Como funciona?

Em termos simples, a notação descreve como o tempo de execução (ou espaço de memória) cresce à medida que os dados de entrada (representados pela letra n) aumentam.

Principais classes de complexidade

Complexidade constante

• Representação: O(1)
• O custo do algoritmo independe do tamanho de n. As instruções são executadas um número fixo de vezes.

// Independentemente do tamanho do vetor, 
// a instrução é executada uma única vez
public static int exemplo1(int[] vetor) {
    return vetor[vetor.length / 2];
}

Complexidade linear

• Representação: O(n)
• O custo do algoritmo cresce linearmente com o tamanho de n. Cada elemento de entrada precisa ser processado uma vez.

// Este algoritmo percorre cada elemento do vetor uma vez, somando os valores
public static int exemplo2(int[] vetor) {
    int soma = 0;
    for (int i = 0; i < vetor.length; i++) {
        soma += vetor[i];
    }
    return soma;
}

Complexidade quadrática

• Representação: O(n²)
• O custo do algoritmo aumenta quadraticamente com o tamanho de n. Normalmente ocorre quando há dois loops aninhados.

// Este algoritmo implementa um método de ordenação, o Bubble Sort
public static void bubbleSort(int[] vetor) {
    int temp;
    for (int i = 0; i < vetor.length - 1; i++) {
        for (int j = 0; j < vetor.length - i - 1; j++) {
            if (vetor[j] > vetor[j + 1]) {
                temp = vetor[j];
                vetor[j] = vetor[j + 1];
                vetor[j + 1] = temp;
            }
        }
    }
}

Complexidade logarítmica

• Representação: O(log n)
• O custo do algoritmo cresce de forma logarítmica com o tamanho de n. É comum em algoritmos de busca ou de divisão e conquista.

// Este algoritmo realiza uma busca binária em um vetor ORDENADO
public static int exemplo4(int[] vetor, int chave) {
    int esquerda = 0;
    int direita = vetor.length - 1;
    while (esquerda <= direita) {
        int meio = esquerda + (direita - esquerda) / 2;
        if (vetor[meio] == chave) {
            return meio;
        }
        if (vetor[meio] < chave) {
            esquerda = meio + 1;
        } else {
            direita = meio - 1;
        }
    }
    return -1;
}

Complexidade e otimização

O gráfico à seguir demonstra, em termos de eficiência de tempo e memória, quais complexidades apresentam melhor desempenho quando os parâmetros de entrada tendem ao infinito:

_{^{Gráfico: https://www.geeksforgeeks.org/analysis-algorithms-big-o-analysis/}}