Algoritmo para encontrar o índice de equilíbrio de um array

Na literatura de algoritmos e estruturas de dados, o índice de equilíbrio de um array é aquele em que a soma dos elementos nos índices menores se iguala à soma dos elementos nos índices maiores.

Analisaremos no decorrer do artigo duas soluções que encontram o índice de equilíbrio de qualquer array passado como parâmetro. A primeira delas irá dispor de uma performance inferior, localizando o índice em complexidade quadrática de tempo. No entanto, a segunda saída para o problema terá um desempenho superior, descobrindo o índice com complexidade linear de tempo.

Entendendo o problema

Uma boa prática antes da elaboração dos algoritmos consiste no entendimento completo do desafio a ser resolvido. Para isso, recomenda-se a observação de exemplos práticos, que ajudem a esclarecer as principais dúvidas referentes ao exercício.

Pressuponha um vetor que armazene sete itens, composto pelos números 4, 9, 2, -5, 6, 1 e 8. O índice de equilíbrio desse array seria o terceiro, no qual reside o número -5. Isso porque a soma dos elementos nos índices menores, ou seja, os índices 0, 1 e 2, resultam em 15, da mesma forma que a soma dos elementos nos índices maiores 4, 5 e 6 totalizam 15.

Sob outra perspectiva, imagine novamente um vetor que detenha sete elementos, desta vez integrado pelos números -4, 1, 9, 6, 2, 7 e -1. Nessa situação, o array não possui um índice de equilíbrio. Nenhuma soma de itens entre os índices à esquerda acaba por ser equiparada com a dos índices à direita. Em cenários assim, o algoritmo pode retornar um valor negativo para indicar a ausência do ponto de equilíbrio.

Usando complexidade quadrática de tempo para resolver o problema

Ainda que existam complexidades de tempo piores, geralmente a complexidade quadrática não se enquadra em um nível aceitável caso a performance do algoritmo seja vital.

Na maioria dos contextos em que uma função apresenta complexidade de tempo quadrática, temos a presença de loops aninhados. Esses laços costumam variar de acordo com o input do método, ou seja, eles percorrem uma estrutura conforme a sua quantidade de elementos.

Se o conceito não estiver tão evidente, considere uma rotina hipotética na qual temos dois loops for, tendo em vista que o segundo deles está dentro do primeiro. O laço mais externo percorre todos os elementos de um array passado como parâmetro, enquanto o laço mais interno executa a mesma ação. Cogitando que o vetor possua quatro itens, o loop aninhado executará dezesseis vezes, isto é, o número de elementos ao quadrado. E esse padrão se repete para arrays de todos os outros tamanhos.

O código acima se responsabiliza por encontrar o índice de equilíbrio em complexidade quadrática de tempo. Perceba que a função inicia com um laço principal, iterando sob os itens do vetor arr. Dentro do loop, temos outras duas estruturas de repetição. Porém, devemos nos atentar, sobretudo, ao laço interno remanescente. Nele, mais uma vez o método está percorrendo os elementos do array arr em sua totalidade, o que acaba caracterizando uma execução quadrática.

Em suma, a ideia por trás do algoritmo está descrita na listagem a seguir.

1. O loop externo é inicializado para percorrer todos os elementos do array arr.
2. A variável somaDaEsquerda é declarada para armazenar a soma dos elementos à esquerda do array arr.
3. O primeiro loop aninhado itera a partir do elemento inicial do array arr até a posição anterior atual do loop externo, de modo a contabilizar a soma dos elementos à esquerda.
4. O segundo loop aninhado itera a partir da posição posterior atual do loop externo até o último elemento do array arr, armazenando a soma dos elementos à direita na variável somaDaDireita.
5. Se o valor de somaDaEsquerda e somaDaDireita forem iguais, ou seja, considerando que o ponto de equilíbrio foi localizado, o índice vigente do loop externo é retornado pela função.
6. Senão, na hipótese do loop externo ter sido percorrido até o final sem encontrar o ponto de equilíbrio, o método retorna um valor negativo.

Usando complexidade linear de tempo para resolver o problema

Quando encontramos a resposta de um problema em complexidade quadrática, a conduta mais adequada baseia-se na construção de uma solução alternativa, que ganhe em eficiência. Frequentemente, há a possibilidade de aperfeiçoar o algoritmo para uma complexidade linear de tempo.

As funções que são classificadas dessa maneira compartilham um comportamento similar. Em boa parte dos casos, o método possui um ou mais loops que percorrem uma estrutura de dados do início ao fim. Melhor dizendo, a execução da rotina varia consoante a quantidade de itens do vetor ou qualquer outra estrutura utilizada.

Inclusive, neste case sob análise, há uma outra abordagem que resolve o desafio em complexidade linear. Para obter o índice que demarca o equilíbrio do array, são executados dois laços for, deslocando-se por todos os elementos.

Em comparação ao algoritmo anterior, a eficiência e simplicidade deste código demonstram uma superioridade notável. A proposta da solução se resume nos seguintes passos.

1. A variável soma é declarada para armazenar a contabilização de todos os elementos do array arr.
2. A variável somaDaEsquerda é declarada para armazenar a contabilização de todos os elementos à esquerda do array arr.
3. O primeiro loop da função percorre o array arr do começo até o final, com o objetivo de calcular a soma de seus itens.
4. O segundo loop da função percorre da mesma forma todos os elementos do array arr, subtraindo os itens à esquerda da variável soma e acrescentando-lhes na variável somaDaEsquerda. Se os valores de ambas as variáveis forem idênticos, o ponto de equilíbrio do vetor terá sido encontrado, e o índice atual do loop é retornado.
5. O método retorna um valor negativo se não tiver detectado o índice de equilíbrio.

Analisando a complexidade das soluções

Até então constatamos que a segunda solução leva vantagem sob a primeira em termos de performance. Contudo, há margem para expandir essa análise. Cabe ressaltar que um algoritmo não deve ser estudado apenas pela óptica da complexidade de tempo, mas também pelo prisma do consumo do espaço auxiliar de memória.

Nesta conjuntura, as duas funções usam um espaço constante de memória. Isso porque nenhuma delas declara outra estrutura de dados no seu corpo, ou executa chamadas recursivas que ocupem a stack do programa. Ambas se beneficiam somente de variáveis simples para controlar a soma de seus elementos.

No que tange a complexidade de tempo, as seções anteriores da publicação já elucidaram a distinção deste aspecto entre os métodos. O primeiro algoritmo desfruta de uma complexidade quadrática, pois trabalha com loops aninhados que variam em detrimento do input. Em contrapartida, a outra função ostenta uma complexidade linear, justamente porque os seus loops não são aninhados.

A análise de algoritmos esmiuçada nos parágrafos anteriores pode ser validada e observada com o suporte da biblioteca BenchmarkDotNet, que calcula indicadores de execução das funções.

Método	Input	Média de tempo	Espaço alocado
MétodoComplexidadeLinear	InputInt32[10]	Média de tempo9.936 ns	Espaço alocado-
MétodoComplexidadeQuadratica	InputInt32[10]	Média de tempo38.492 ns	Espaço alocado-
MétodoComplexidadeLinear	InputInt32[50]	Média de tempo43.118 ns	Espaço alocado-
MétodoComplexidadeQuadratica	InputInt32[50]	Média de tempo854.111 ns	Espaço alocado-
MétodoComplexidadeLinear	InputInt32[100]	Média de tempo104.201 ns	Espaço alocado-
MétodoComplexidadeQuadratica	InputInt32[100]	Média de tempo3,736.736 ns	Espaço alocado-
MétodoComplexidadeLinear	InputInt32[500]	Média de tempo475.159 ns	Espaço alocado-
MétodoComplexidadeQuadratica	InputInt32[500]	Média de tempo16,460.905 ns	Espaço alocado-

Nas quatro simulações geradas, em todas elas a rotina ComplexidadeLinear foi superior à ComplexidadeQuadratica. Aliás, reparando com mais cuidado, o método ComplexidadeLinear, mesmo no cenário com quinhentos elementos, deixou para trás o procedimento ComplexidadeQuadratica. A cada teste, a distância de tempo entre as funções só aumentou.

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.