Algoritmo para encontrar a frequência em um array ordenado

Levando em consideração as estruturas de dados existentes na área da programação, os arrays sem dúvida alguma participam do grupo das que mais se destacam. Embora a manipulação de vetores seja simples na maioria das vezes, eles auxiliam na resolução de muitos algoritmos conhecidos pelos desenvolvedores de software.

A computação da diferença máxima entre elementos, a localização do índice de equilíbrio e a remoção de itens duplicados representam uma pequena amostra dos problemas solucionados com o uso da estrutura em questão.

Neste artigo, o algoritmo para encontrar a frequência em um array será estudado a partir de duas implementações únicas. Como veremos, a diferença entre elas residirá no espaço auxiliar de memória consumido durante a execução das respectivas funções.

Entendendo o problema

Antes de pensar nos detalhes técnicos, o entendimento geral do problema se faz necessário para facilitar a elaboração e análise dos algoritmos. Tendo isso em vista, o objetivo principal deste desafio envolve o cálculo da quantidade de aparições de todos os elementos presentes no array de input.

De modo complementar, há também uma precondição que impacta na lógica do exercício. Obrigatoriamente, o vetor examinado deve estar ordenado. Essa regra, de certa maneira, reduz bastante a dificuldade imposta pelo problema.

Portanto, pressuponha um array composto pelos itens [1, 1, 3, 3, 3, 3, 5, 7, 7, 7, 7, 7, 7]. Com base em uma rápida observação, se conclui que a frequência do número um é igual a dois, enquanto a do número três é de quatro, a do número cinco é de um, e, por fim, a do número sete é de seis.

Usando complexidade linear de espaço para resolver o problema

Em boa parte das ocasiões, comparamos e analisamos os algoritmos sob a óptica da complexidade de tempo. Contudo, ambas as soluções que localizam a frequência dos elementos nos vetores ordenados executam em uma mesma velocidade. Quando isso acontece, costumeiramente a distinção de performance está no uso do espaço auxiliar de memória.

A complexidade linear de espaço está relacionada às funções que declaram e utilizam outras estruturas de dados que variam em tamanho de acordo com o input recebido por parâmetro.

Por exemplo, imagine um método que obtenha como argumento um vetor. Na hipótese desse procedimento definir um segundo array no seu corpo que tenha a capacidade de armazenamento dependente da estrutura original, podemos afirmar que a função acaba consumindo um espaço auxiliar de memória linear.

O algoritmo acima localiza a frequência dos elementos no array arr aplicando justamente os conceitos de uma função qualquer que possui complexidade linear de memória. A justificativa para isso está no fato de que o método se faz valer de um dicionário que replica os itens do vetor.

1. A variável dict é declarada para contabilizar a frequência de cada item do array arr.
2. O primeiro loop da função percorre todos os elementos do array arr, checando iteração a iteração se o dicionário dict já iniciou a contagem para o item atual. Em caso afirmativo, ele somente incrementa a contabilização. Senão, adiciona o elemento no seu controle com a frequência igual a um.
3. Por fim, o segundo loop do método itera pela estrutura dict, exibindo a quantidade de aparições dos itens no array arr.

Usando complexidade constante de espaço para resolver o problema

Conforme evidenciado na seção anterior, uma função recebe a classificação de complexidade linear de memória se possuir uma estrutura de dados adicional que varie de comprimento em detrimento do input. Isso pode se tornar um impedimento para algoritmos que precisem processar um volume grande de dados.

Assim como existem soluções alternativas para melhorar a complexidade de tempo de um método, neste caso em específico há uma variação do algoritmo que encontra a frequência nos vetores ordenados utilizando complexidade constante de espaço. Ou seja, independente do input, a função consome praticamente a mesma quantidade de memória.

Examinando o código do método, fica simples de perceber que a diferença principal no que diz respeito à função de complexidade linear é propriamente a ausência de uma estrutura de dados auxiliar. No entanto, isso não impede que o algoritmo resolva o problema.

1. A variável frequencia é declarada para manter o controle de quantas vezes um determinado elemento está presente no array arr.
2. O único loop da função percorre os itens do array arr até a última posição, iniciando a iteração no segundo item. A cada varredura, o laço verifica se o elemento atual é igual ao anterior. Se essa condição for verdadeira, a variável frequencia sofre um incremento. Caso contrário, a frequência total para o item sendo analisado é exibida, e o valor da variável frequencia retorna para um.
3. Antes do término do método, apresenta-se a frequência relativa ao último item do array arr. 

Analisando a complexidade das soluções

No que tange o espaço auxiliar de memória, o primeiro algoritmo demonstrado se notabilizou por ter uma complexidade linear, dependente do input da função. Em contrapartida, o segundo algoritmo melhorou esse cenário, alcançando uma complexidade constante.

Já quanto a complexidade de tempo, os dois métodos se equivalem, afinal de contas as suas execuções são lineares. Isso se explica pelo fato que os algoritmos possuem loops simples na sua definição, percorrendo uma quantidade de elementos atrelada sempre ao array de input.

Os indicadores de performance das funções calculados pela biblioteca BenchmarkDotNet fornecem maior transparência na compreensão das complexidades. Porém, cabe ressaltar que os critérios do framework para estabelecer o tamanho do espaço alocado dispõem de suas próprias particularidades. Por isso que o MétodoComplexidadeConstante acaba manifestando uma variação no uso da memória.

Método	Input	Média de tempo	Espaço alocado
MétodoComplexidadeConstante	InputInt32[18]	Média de tempo847.0 μs	Espaço alocado641 B
MétodoComplexidadeLinear	InputInt32[18]	Média de tempo856.9 μs	Espaço alocado1417 B
MétodoComplexidadeConstante	InputInt32[51]	Média de tempo2,037.8 μs	Espaço alocado1522 B
MétodoComplexidadeLinear	InputInt32[51]	Média de tempo2,024.1 μs	Espaço alocado3090 B
MétodoComplexidadeConstante	InputInt32[128]	Média de tempo3,957.9 μs	Espaço alocado2965 B
MétodoComplexidadeLinear	InputInt32[128]	Média de tempo3,876.9 μs	Espaço alocado4530 B
MétodoComplexidadeConstante	InputInt32[203]	Média de tempo5,353.5 μs	Espaço alocado4005 B
MétodoComplexidadeLinear	InputInt32[203]	Média de tempo5,322.2 μs	Espaço alocado7405 B

Ao passo que a média de tempo dos algoritmos caminha em uma proximidade notável, a diferença entre o uso do espaço auxiliar pelas funções se sobressai. Em circunstâncias como no exemplo do vetor de cinquenta e um elementos, o MétodoComplexidadeLinear consumiu mais do que o dobro de memória para completar a sua execução. Esse é o preço que a função paga por depender de um dicionário de tamanho N.

O código-fonte completo dos algoritmos e os detalhes extras acerca do desempenho de cada um deles estão disponíveis no meu repositório do Github.