Notação Big-O: complexidade de tempo

Otimização de Código em Java

Pavlos Kosmetatos

Lead Engineer @Wealthyhood

O que é complexidade de tempo?

Complexidade de tempo: mede como o tempo de execução cresce com o tamanho da entrada
Ajuda a responder: "O que acontece se meus dados ficarem 10× maiores?"
Não foca no tempo absoluto

Notação Big-O

Notação matemática para descrever o pior caso.

Algumas classes comuns de complexidade:

O(1): Tempo constante - independente do tamanho

Entendendo O(1)

Um exemplo de operação O(1) é o get() do ArrayList

Implementação interna (simplificada) de um ArrayList que guarda Strings:

public class ArrayList {}
    private String[] data; // Internal array
    private int size;

    // Get operation - direct array access
    public String get(int index) {
        return data[index]; // O(1)
    }
}

Notação Big-O

Notação matemática para descrever o pior caso

Algumas classes comuns de complexidade:

O(1): Tempo constante - independente do tamanho
O(n): Tempo linear - cresce com a entrada

Entendendo O(n)

Um exemplo semelhante, mas para contains() do ArrayList

public boolean contains(Object o) {
    return indexOf(o) >= 0;
}

public int indexOf(Object o) {
    // Linear search through array
    for (int i = 0; i < size; i++) {
        if (o.equals(elementData[i])) {
            return i;
        }
    }
    return -1; // Not found
}

Notação Big-O

Notação matemática para descrever o pior caso

Algumas classes comuns de complexidade:

O(1): Tempo constante - independente do tamanho
O(n): Tempo linear - cresce com a entrada
O(n²): Tempo quadrático - cresce quadraticamente com a entrada

Um exemplo prático com complexidade quadrática

// Finding a pair of numbers that sum to a target value
// Time complexity: O(n²)

public int[] findPairWithSum(ArrayList<Integer> numbers, int targetSum) {
    for (int i = 0; i < numbers.size(); i++) {
        for (int j = i + 1; j < numbers.size(); j++) {
            if (numbers.get(i) + numbers.get(j) == targetSum) {
                console.log("Found them!")
            }
        }
    }
}

Por que a complexidade de tempo importa

Impacto do tamanho da entrada:

O(1): 1.000 -> 1.000.000 itens = Mesmo tempo!
O(n): 1.000 -> 1.000.000 itens = 1.000× mais lento
O(n²): 1.000 -> 1.000.000 itens = 1.000.000× mais lento

Screenshot 2025-05-10 at 2.27.06 PM.png

Vamos praticar!

Otimização de Código em Java