Complexidade de Algoritmos-Modificações in-place com O(1) de memória extra

Em 2021 pretendo aprofundar aos poucos meu conhecimento em Algoritmos e Estruturas de dados. A ideia será analisar algoritmos clássicos e buscar entender conceitos como Notação Big-O, Divisão-Conquista e Programação Dinâmica.

Reverse String

O primeiro algoritmo que analisado foi o reverseString. Apesar de simples, o enunciado do algoritmo possui alguns conceitos interessantes de serem observados:

Escreva uma função que reverte uma string. O texto de entrada é dado como um array de caracteres do tipo char[]. Não aloque espaço extra para outro array e você precisa modificar o array de entrada in-place com O(1) de memória extra. Você precisa assumir que todos os caracteres consistem em printable ascii characters.

Abaixo faço algumas considerações do meu entendimento a respeito de dois conceitos abordados na descrição: modificações in-place e O(1) de memória extra.

Complexidade de Algoritmos

Conforme explicado brilhantemente pelo Hallison Paz no vídeo abaixo, a Complexidade é uma medida da quantidade de recursos que são demandados por um algoritmo. E estes recursos são divididos entre medidas de tempo e de espaço.

Ou seja, analisar a complexidade de um algoritmo consiste em: observar quais recursos ele utiliza que podem aumentar ou diminuir a quantidade de tempo e espaço computacional (memória) pra solucionar o problema.

Dependendo da implementação, o valor de memória utilizado pode ser inviável para o dispositivo em que ele está executando (dispositivos embarcados por exemplo, tem memória limitada) e o valor de tempo pode ser impraticável para nós seres humanos esperarmos o resultado (podendo chegar a séculos).

Como todo algoritmo possui uma entrada e uma saída (no escopo de algoritmos que iremos estudar) um algoritmo in-place se propõe a entregar o seu resultado, transformando a entrada em uma saída. Economizando espaço e variáveis adicionais.

In-Place

Antes de abordar a complexidade desse algoritmo usando a notação Big-O acredito que seja importante exemplificar o conceito de algoritmo in-place. Para isso, vamos iniciar analisando a resolução do problema com uma estratégia que não o utiliza essa ideia.

Basicamente, essa função em C# recebe uma lista de caracteres (listaCaracteres) cria um array auxiliar (revertedArr) e faz uma interação na lista buscando os caracteres de trás para frente e colocando na estrutura revertedArr.

Como pode ser verificado pelo gerenciador de testes do Visual Studio, esta implementação funciona relativamente bem (511ms para uma massa de dados considerável).

Porém, há alguns detalhes nesse algoritmo que podem ser melhorados.

1ª Re-fatoração no código: colocação doWhile

O for pode ser substituído por um do While, removendo a necessidade da existência de dois contadores presentes no código (veja que o contador i foi eliminado e a propriedade length do array s passou a ser utilizado como índice).

2ª Re-fatoração do código: transformação num código in-place

Neste código abaixo, o array auxiliar utilizado nos códigos anteriores foi removido. E o array “s” passou a ser utilizado tanto na Entrada quanto na saída do Algoritmo.

Veja também que a interação não é mais necessária até o fim do array, pois quando a execução chega na metade deste array as permutações de início e fim já foram concluídas.

Esta é a solução in-place para o problema proposto.

Complexidade de espaço O(1)

Mas como saber se a solução proposta é uma solução de complexidade O(1)?

Há diversos materiais sobre Complexidade de Espaço na Internet, porém o que mais me trouxe clareza a respeito do tema foi o do Koding Kevin, linkado abaixo:

Como já adiantei acima, os algoritmos tem 2 tipos de complexidade: de espaço e de tempo. Porém, há algumas regras importantes na análise de complexidade de espaço:

1 — Valores primitivos numéricos e booleanos geralmente possuem complexidade O(1) porque ocupam um espaço constante na memória.

Portanto, var x = 100 ocupa o mesmo espaço de var x=200. (ainda não tenho informações detalhadas se conversões de tipos numéricos como double pra float por exemplo, influenciam de forma significativa, então vou desconsiderar esses casos por enquanto).

2 — Strings, Arrays e Objetos possuem complexidade de espaço linear O(n). Ou seja, o tamanho da entrada irá influenciar no tamanho de memória que será ocupada pelo algoritmo.

Portanto, um array de 4 elementos ocupa o dobro de espaço, que um array de 2 elementos.

Sendo assim, o nosso primeiro algoritmo possui uma complexidade de espaço O(n). Pois o comprimento do array “s” pode variar e esta variação afeta o comprimento do array “revertedArr” (linha 4).

Já o último algoritmo apresentado possui complexidade O(1), pois o tamanho de posições de memória ocupadas no seu processamento não vai crescer de acordo com o tamanho do array de entrada.

Este fato acontece pelo fato de estarmos utilizado apenas variáveis primitivas no seu desenvolvimento (aux e cont).

Conclusão

Apesar de fugir da descrição do problema proposto, é interessante observar que, apesar da solução final ser melhor em termos de complexidade de espaço ela não é tão eficiente quando analisamos a complexidade de tempo.

A minha hipótese é que, a primeira solução executa apenas duas instruções dentro do loop (uma atribuição e uma soma):

Já a segunda executa 3 atribuições (linhas 3,4,5) uma soma (linha 6) e ainda finaliza com uma comparação (7).

Ou seja, a solução final gasta menos espaço mas executa uma quantidade maior de passos. O desempenho dos testes saiu de 511 milissegundos pra 3,1 segundos utilizando a mesma máquina e os mesmos valores de entrada.

Todos os autores que pesquisei relataram que a Complexidade de Tempo sempre possui prioridade em relação a Complexidade de Espaço.

Porém, acredito que em contextos em que a memória do dispositivo onde o algoritmo irá ser executado possui limitações (os já citados dispositivos embarcados por exemplo) a complexidade de Espaço pode ter mais relevância.

É uma discussão Arquitetural, que apesar de tentadora, foge do escopo desse artigo.

Problema técnico encontrado na implementação

Pra finalizar, acho interessante relatar um incidente que tive com o framework de BDD/TDD que utilizei para realizar os testes unitários: FluentAssertions.

Por algum motivo que ainda não tive tempo de pesquisar, a cláusula BeEquivalentTo possui um significado léxico perigosamente dúbio. No caso deste algoritmo em si, as palavras “cezar” e “ceazr” são consideradas como corretas. Assim como “cezar” e “razec”.

Na dúvida, utilize a cláusula equals quando for necessário comparar dois array’s de char.

Um abraço, obrigado pela leitura e fique a vontade para comentar.