Algoritmo para encontrar o elemento majoritário de um array

Os arrays são estruturas de dados que possuem um catálogo vasto de algoritmos relevantes. O cálculo do subarray de soma máxima, a busca pelo índice de equilíbrio e a remoção de elementos duplicados são apenas alguns exemplos que sustentam a afirmação anterior.

Esta publicação dará um passo adiante na análise dos algoritmos de vetores, detalhando como encontrar o elemento majoritário de um array. Conforme o procedimento padrão, tanto a solução com pior complexidade de tempo, quanto a com melhor complexidade de tempo, serão devidamente apresentadas e comparadas.

Entendendo o problema

Para que um algoritmo seja elaborado ou até mesmo compreendido, o desenvolvedor precisa a princípio aprender sobre o problema em questão. Neste caso, o conceito fundamental no entendimento do desafio se trata justamente do elemento majoritário.

De acordo com a definição formal, um elemento majoritário em um array de tamanho n é aquele que está presente mais de n/2 vezes na estrutura. Logo, não existe mais que um item desse tipo em qualquer vetor.

Exemplificando, imagine um array hipotético que armazene os elementos 1, 5, 4, 5, 5, 5, 1, 5, 5. De maneira evidente, o vetor contém o total de nove itens, sendo que somente o número cinco tem seis aparições. Portanto, cinco seria o elemento majoritário, pois supera a marca de n/2 (9/2) ocorrências.

Usando complexidade quadrática de tempo para resolver o problema

O método mais básico e de pior complexidade de tempo consiste na execução de dois loops que mantenham a maior contagem para todos os elementos. Se essa quantidade exceder o valor de n/2, então os laços são interrompidos e o item que alcançou tal marca é retornado. Nos cenários em que a contagem não ultrapassar o limite de n/2, isto significa que o elemento majoritário está ausente no array.

Assim como na maioria dos algoritmos de complexidade quadrática de tempo, a estrutura de repetição for aninhada e dependente do input, faz com que a função tenha uma performance inferior.

Em linhas gerais, as instruções do algoritmo estão enumeradas a seguir.

1. A variável contagemMaxima é declarada para controlar a quantidade de aparições do item de principal frequência no array.
2. A variável indice é declarada para manter a posição do item de principal frequência no array.
3. O loop externo for percorre todos os elementos do vetor, e a cada iteração, declara a variável contagem para determinar a quantidade de aparições do item sendo varrido.
4. O loop aninhado for inicia outra busca completa no array, incrementando o valor da variável contagem para cada elemento que no índice j for o mesmo que no índice i.
5. A iteração do loop externo se encerra a partir da validação de uma cláusula if, que checa se a contagem atual superou a contagemMaxima. Em caso positivo, os valores das variáveis contagemMaxima e indice são atualizadas, com o intuito de refletir qual é o novo elemento com mais aparições.
6. Fora do loop externo, a execução do método é encerrada através da verificação de outra condicional, que desta vez indica se a contagemMaxima excedeu o valor de n/2. Ou seja, este if inspeciona se o array possui ou não um elemento majoritário.

Usando complexidade linear de tempo para resolver o problema

A forma mais eficiente para solucionar o problema advém do algoritmo majoritário de Moore. Basicamente, esse algoritmo possui duas etapas substanciais que permitem encontrar o elemento majoritário de um array em complexidade linear de tempo.

1. O primeiro estágio do algoritmo fornece um elemento majoritário em potencial que esteja no vetor. Se tal item realmente existir, esta etapa retornará o número procurado, caso contrário, retornará um candidato.
2. O segundo estágio do algoritmo verifica se o elemento obtido é de fato majoritário.

A listagem abaixo específica cada uma das ações aplicadas no algoritmo de Moore.

1. A função EncontrarCandidato é chamada para pesquisar por um provável elemento majoritário.
2. Já no escopo do método EncontrarCandidato, as variáveis indiceCandidato e contagem são declaradas, de modo a armazenar o índice do possível elemento majoritário e a quantidade de aparições em sequência deste mesmo elemento no array, respectivamente.
3. Um loop for percorre todos os elementos do vetor a partir da sua segunda posição. A cada iteração, duas verificações são executadas. A primeira delas, composta pelo bloco de código if/else, checa se o elemento no indiceCandidato é igual ao elemento no índice sequencial i. Em caso positivo, a variável contagem é incrementada, senão, a própria variável é decrementada. Por outro lado, a segunda condicional valida se a variável contagem está zerada. Nessa situação, o indiceCandidato passa a ser o índice i percorrido, e a contagem retorna para o seu valor inicial.
4. Terminado o laço de repetição, o elemento localizado no indiceCandidato é retornado.
5. A execução volta para a função principal, que desta vez invoca o método ChecarSeElementoMajoritario para garantir que o elemento candidato também é o elemento majoritário do vetor.
6. Resumidamente, a rotina ChecarSeElementoMajoritario varre novamente os elementos do array, mas com o objetivo de contar quantas ocorrências do elemento candidato estão presentes na estrutura. Na última linha de código da função, o valor da variável contagem é comparado com o resultado da divisão de n/2 para determinar se o elemento candidato é majoritário.
7. Mais uma vez, a execução retorna para a função principal. Se o resultado da expressão final de ChecarSeElementoMajoritario tiver sido verdadeiro, o elemento candidato é exibido como o elemento majoritário do vetor.

Analisando a complexidade das soluções

Após uma análise minuciosa referente às duas soluções, constatou-se que quanto a complexidade de tempo, o primeiro algoritmo apresenta um desempenho quadrático. Isso porque os elementos do array passados por parâmetro na função são percorridos de maneira aninhada, fator que interfere negativamente na execução do método para inputs maiores.

Contudo, o segundo algoritmo se destacou por eliminar os loops aninhados, localizando o elemento majoritário do vetor em complexidade linear de tempo. Em outras palavras, esta função se comporta muito melhor no processamento de arrays com uma quantidade considerável de itens.

Método	Input	Média de tempo	Espaço alocado
MétodoComplexidadeLinear	InputInt32[10]	Média de tempo124.7 μs	Espaço alocado-
MétodoComplexidadeQuadratica	InputInt32[10]	Média de tempo128.3 μs	Espaço alocado-
MétodoComplexidadeLinear	InputInt32[50]	Média de tempo125.4 μs	Espaço alocado-
MétodoComplexidadeQuadratica	InputInt32[50]	Média de tempo123.4 μs	Espaço alocado-
MétodoComplexidadeLinear	InputInt32[200]	Média de tempo124.2 μs	Espaço alocado-
MétodoComplexidadeQuadratica	InputInt32[200]	Média de tempo131.4 μs	Espaço alocado-
MétodoComplexidadeLinear	InputInt32[1000]	Média de tempo131.2 μs	Espaço alocado-
MétodoComplexidadeQuadratica	InputInt32[1000]	Média de tempo1,101.8 μs	Espaço alocado1 B

As métricas do quadro acima, geradas através da ferramenta BenchmarkDotNet, comprovam que o MétodoComplexidadeLinear obtém uma larga vantagem no tempo de execução em detrimento do MétodoComplexidadeQuadratica, sobretudo quando o input começa a crescer. Perceba que a diferença de tempo de computação entre o menor input para o maior input foi de apenas 6.5 μs na função linear, enquanto na função quadrática a diferença alcançou o patamar de 973,5 μs (cerca de 149 vezes a mais).

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