Primeira vez aqui? Seja bem vindo e cheque o FAQ!
x

Ache a soma de todos os números menores que 2 milhões. Essa solução é eficiente? Discuta a eficiência da sua solução.

+1 voto
77 visitas
perguntada Mar 20 em Programação Computacional por Fernando Fellows (11 pontos)  
Compartilhe

2 Respostas

+1 voto
respondida Mar 20 por Fernando Fellows (11 pontos)  
editado Set 10 por Fernando Fellows
 
Melhor resposta

A maneira mais direta, mas menos sofisticada de se calcular esse valor é realizando a conta de valor em valor de 1 a 1.999.999. Dessa forma, serão realizadas as contas:
1+2=3
3+3=6
6+4=10
10+5=15
.
.
.
1999997000001+1999999=1999999000000
Portanto, a máquina será obrigada a realizar n-1 contas, o que não pode ser considerado eficiente, a partir da solução em Python:

-> Achar a soma de todos os números menores que 2 milhões.
sum(range(1,2000000))

1999999000000
#

Uma maneira um pouco mais sofisticada, de uma forma muito mais matemática do que de programação, podemos utilizar o somatório rápido de uma sequência numérica, conhecida como Soma de Gauss.
Simplificando a intuição desta soma, levamos em conta a soma dos extremos, isto é, os pares de mínimo e máximo, após a utilização dos mínimos e máximos anteriores.
Com isto, teremos a conta:
1+1.999.999= 2.000.000
2+1.999.999=2.000.000
....
até que teremos
999.999+1.000.001= 2.000.000
Este resultado se repete n/2 vezes, de forma que reorganizamos nossa função para:

x = (n/2)(n+1) ou x = (n(n+1))/2
Desta forma, ao realizar essa equação a máquina será somente obrigada a calcular uma única função, o que é extremamente eficiente se comparado com n-1 vezes, especialmente quando n tende a infinito.
Calculando em Python:

x=(1999999*(1999999+1))/2

print(x)
1999999000000

O resultado em ambas equações foi exatamente o mesmo, no entanto, a eficiência da segunda forma foi muito superior.

0 votos
respondida Ago 15 por Rodrigo Stuckert (46 pontos)  

Fernando, tudo bem?

Achei sua resposta muito boa. Você foi capaz de apresentar tanto uma solução ingênua, resolvendo o problema pela definição usando força bruta, como também uma resolução consideravelmente mais eficiente usando conceitos algébricos.
Assim, não tenho formas de resolução melhores pra apresentar, mas quero aqui trazer uma interpretação mais visual para a solução que você apresentou.

Seja \(\{a_{1}, a_{2}, a_{3}, ..., a_{n}\}\), uma sequência numérica, tal que \(a_{1} = 1\). Então, a soma \(S_{n}\) dos \(n\) primeiros termos dessa sequência será dada pela seguinte equação:

\[S_{n} = \sum_{i = 1}^{n} a_{i} = \dfrac{n (n + 1)}{2}\]

Para visualizar o problema, primeiro crie colunas enfileiradas representando cada um dos \(n\) termos. Note que seria possível formar um retângulo de área \(A = n(n+1)\) ao colocar outra figura de mesma forma virada para baixo sobreposta à nossa figura original. Consequentemente, a área de cada uma dessas formas deverá ser igual a \(\dfrac{n(n+1)}{2}\), Q.E.D.

A imagem será apresentada aqui.
Exemplo para \(n = 4\)

...