Como é que a complexidade dos algoritmos é medida e descrita?

A complexidade dos algoritmos é geralmente medida em termos de complexidade temporal e espacial, que descrevem como o número de operações (tempo) e a memória utilizada (espaço) crescem em função do tamanho dos dados de entrada.

A notação mais comum utilizada é a notação "Big O", que mostra o limite superior do crescimento do consumo de recursos do algoritmo ao aumentar os dados de entrada. Por exemplo:

• O(1) — complexidade constante, o tempo não depende do tamanho da entrada.
• O(n) — linear, o tempo cresce proporcionalmente ao tamanho da entrada.
• O(n²) — quadrática, o tempo cresce proporcionalmente ao quadrado do tamanho da entrada.

Exemplo em Java para calcular a soma dos elementos de um array com complexidade linear O(n):

public int sum(int[] arr) {
    int total = 0;
    for (int num : arr) {
        total += num;
    }
    return total;
}

Aqui, o tempo de execução depende do comprimento do array, portanto a complexidade é — O(n). A avaliação de algoritmos ajuda a escolher as soluções mais eficientes, especialmente ao trabalhar com grandes volumes de dados.