Notação Big-O: complexidade de espaço

Otimização de Código em Java

Pavlos Kosmetatos

Lead Engineer @Wealthyhood

O que é complexidade de espaço?

A complexidade de tempo descreve como o tamanho da entrada afeta o tempo de execução
A complexidade de espaço descreve como o tamanho da entrada afeta o uso de memória

Entender a complexidade de espaço é crucial para criar aplicações que:

Usem apenas a memória necessária, sem excessos
Evitem falhas como OutOfMemoryError

Notação Big-O

A notação é idêntica à da complexidade de tempo.

Algumas classes comuns:

O(1): Constante — independente do tamanho
O(n): Linear — cresce com a entrada
O(n²): Quadrática — cresce quadraticamente com a entrada

Um método que encontra o máximo

public int findMax(int[] array) {
    int max = Integer.MIN_VALUE;
    for (int value : array) {
        if (value > max) {
            max = value;
        }
    }
    return max;
}

Tenha o array 10 ou 10 milhões de elementos, ainda usamos memória para uma única variável, max
A complexidade de espaço é O(1), ou constante

Um método que dobra valores

public int[] doubleValues(int[] array) {
    int[] result = new int[array.length];
    for (int i = 0; i < array.length; i++) {
        result[i] = array[i] * 2;
    }
    return result;
}

Se a entrada tem n elementos, precisamos de espaço para n elementos adicionais
A complexidade de espaço é O(n) porque a memória extra cresce linearmente com o tamanho da entrada

Um método de tabela de multiplicação

public int[][] multiplicationTable(int n) {
    int[][] table = new int[n][n];
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            table[i][j] = (i + 1) * (j + 1);
        }
    }
    return table;
}

Se n for 10, precisamos de 100 células; se n for 100, precisamos de 10.000 células
Classificamos como O(n²)

Por que a complexidade de espaço é importante?

Memória é um recurso finito!

Nossos exemplos anteriores com 10.000 elementos de entrada:

findMax, O(1) -> apenas alguns bytes extras
doubleValues, O(n) -> cerca de 40 KB de memória extra
multiplicationTable, O(n²) -> cerca de 400 MB de memória extra

Gráfico de barras mostrando aumento de 8 bytes para findMax, 40 KB para doubleValues e 400 MB para multiplicationTable

Complexidade de espaço vs. complexidade de tempo

Não esqueça:

Às vezes trocamos espaço por tempo
Às vezes trocamos tempo por espaço
A escolha certa depende das suas restrições

Gráfico simbolizando o trade-off entre tempo e espaço

Vamos praticar!

Otimização de Código em Java