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.

0 votos
51 visitas
perguntada Mar 20 em Programação Computacional por Fernando Fellows (1 ponto)  
Compartilhe

1 Resposta

0 votos
respondida Mar 20 por Fernando Fellows (1 ponto)  
 
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=4
4+4=8
8=5=13
.
.
.
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.

...