Complexidade de Espaço dos Algoritmos

Eai, cês tão bem?

Nesse meu post falei sobre complexidade de tempo dos algoritmos e hoje pra finalizarmos esse tópico de complexidades, irei falar um pouco sobre a complexidade de espaço. Bora lá? 🌚

ps: Usarei python para explicar alguns conceitos

O que é complexidade de espaço 🪐

No post que citei acima falei sobre a complexidade de tempo, que, em resumo, diz respeito à "quantidade de tempo" que um algoritmo precisa para executar. Agora, vamos de falar sobre a complexidade de espaço, que se refere à quantidade de memória necessária para executar um algoritmo. Em termos simples, a complexidade de espaço é expressa considerando a quantidade de memória adicional utilizada em relação ao tamanho da entrada fornecida ao nosso algoritmo.

👀 Dê uma olhada no código abaixo:

def doubled_number(numbers):
    result = []
    for number in numbers:
        result.append(number * 2)
    return result

O que fazemos aqui é percorrer cada elemento do array passado como parâmetro, multiplicá-lo por dois e adicioná-lo a um novo array chamado result.

Podemos concluir, então, que se eu passar um array com 100 números, ele me retornará um novo array com 100 números. Da mesma forma, se eu passar um array com 10 elementos, o resultado será um novo array com 10 elementos.

"Então, Ana, qual conclusão tiramos disso tudo?" Quanto mais a entrada cresce, a saída também cresce e, consequentemente, o espaço ocupado por ela também aumenta. Isso implica dizer que a Complexidade de Espaço é dada por O(n).

Vamos ver outro exemplo agora:

def sum_list(numbers):
    sum = 0
    for number in numbers:
        sum += numero
    return sum

A função acima percorre uma lista de números, soma todos eles e, no final, retorna o resultado dessa soma.

A complexidade de espaço para essa função é O(1), ou seja, constante. Isso ocorre porque a função utiliza apenas uma variável adicional, sum, para armazenar todo o resultado acumulado.

Independentemente do tamanho do array de entrada, a quantidade de espaço necessária para a variável soma permanece constante.

De forma prática, a complexidade de espaço O(1) significa que o consumo de memória da função não aumenta com o tamanho do array. Mesmo se o array tiver milhões de elementos, a função ainda exigirá a mesma quantidade de espaço adicional para a variável sum.

👀 E pra finalizarmos vale super a pena dar uma olhada neste site aqui, que mostra a complexidade em um gráfico e pode ajudar a entender, especialmente em relação à notação Big O, utilizada para descrever a eficiência de algoritmos em termos de tempo e espaço. Se tiver dúvidas sobre isso, falei mais a respeito neste meu artigo aqui.

Espero ter ajudado! 😊

bjs bjs e até a próxima 💟