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

Como prover a soma dos N primeiros quadrados de inteiros?

0 votos
34 visitas
perguntada Set 29 em Ciência da Computação por Henrique Alves (11 pontos)  
Compartilhe

1 Resposta

0 votos
respondida Set 29 por Henrique Alves (11 pontos)  

Olá a todos :)

Hoje vamos tratar de um assunto muito interessante, que é a eficiência de algoritmos. O exercício em questão é o 3.6 do livro Introduction to Recursive Programming.

Queremos basicamente buscar uma forma de fugir da recursão, o que pode ser interessante para várias aplicações.

Antes disso, vamos considerar a seguinte expressão:

\(\sum_{i=1}^{n} i = \frac{n(n+1)}{2} \) (1)

Ou seja, essa expressão nos dá o valor da soma dos n primeiros números inteiros. Vamos usar isso na solução do problema!!

O desafio proposto na questão é:

Use a expressão \( \sum_{i=1}^{n}\frac{i(i+1)}{2} = \sum_{i=1}^{n} i(n-i+1) \) para calcular os n primeiros quadrados de inteiros: 1²+2²+3²+...+n²

Usando um método recursivo, teríamos um um algoritmo da forma:

n = int(input('Entre o valor de n: '))

def func1(n):
    if n == 1:
        return 1
    if n!= 1:
        return func1(n-1)+n**2

if __name__ == '__main__':
    print(func1(n)

Mas seguindo a proposta da questão, vamos fazer algumas contas:

\( \sum_{i=1}^{n}\frac{i(i+1)}{2} = \sum_{i=1}^{n} i(n-i+1) \)

\( \sum_{i=1}^{n} i^{2}/2 + \sum_{i=1}^{n} i/2 = \sum_{i=1}^{n} in - \sum_{i=1}^{n} i^{2} + \sum_{i=1}^{n} i \)

\( \frac{3}{2}\sum_{i=1}^{n} i^{2} = \sum_{i=1}^{n} in + \sum_{i=1}^{n} \frac{i}{2} \)

porém, lembrando da expressão (1) descrita acima:

\( \frac{3}{2}\sum_{i=1}^{n} i^{2} = \sum_{i=1}^{n} in + \frac{n(n+1)}{4} \)

\( \frac{3}{2}\sum_{i=1}^{n} i^{2} = \frac{n^{3}+n^{2}}{2}+\frac{n^{2}+n}{4} \)

\( \sum_{i=1}^{n} i^{2} = \frac{n}{6}(2n^{2}+3n+1) \) (2)

Com essa expressão fica fácil calcular o nosso valor =D

O algoritmo seria:

n = int(input('Entre o valor de n: '))

def quadrado(n):
    sum = (n/6)*(2*n**2+3*n+1)
    return sum

if __name__ == '__main__':
    print(quadrado(n))

"Mas Henrique, e com relação à eficiência do algoritmo?"

Bem, para esse problema eu posso dizer que a resposta para isso é bastante simples. Vamos calcular o tempo de execução dos programas usando os seguintes comandos:

import time

inicio = time.time()   

**Linha de código**

fim = time.time()
print(fim - inicio)

Dessa forma podemos calcular o tempo de execução de cada programa. Para n = 800000, o tempo de execução para o programa de recursão foi de 4.0223 ms, enquanto para o programa que utiliza a expressão (2) o tempo foi de 3.3623 ms. Pode parecer muito pequena a diferença dos tempos, mas vamos considerar primeiramente a simplicidade do programa e que a partir de um valor muito elevado para n a execução pode ficar muito onerosa ao computador.

Comentários finais:

Com certeza esse método é muito bom em reduzir o tempo de execução e melhorar a eficiência dos algoritmos. Contudo, para funções mais complexas, fazer essas transformações vão exigir um pouco mais de matemática...

As respostas aqui foram baseadas no capítulo 3 do livro (que por sinal é muito bom!), e lá existem algumas informações de como faríamos para funções mais complexas do que .

Por hoje é isso pessoal;
Cheers :)

comentou Out 6 por Fabio Fujita (46 pontos)  
Olá Henrique!

Parabéns pela solução!

A questão exemplifica bem uma das idéias principais do capítulo 3 do livro Introduction to Recursive Programming do Manuel Rubio Sanchez, que é a de reduzir a complexidade do algoritmo e/ou tempo de execução manipulando as recursões que serão executadas.

Alguns comentários:

1. Ao longo da sua solução você descreve o enunciado da questão e especifica de onde ela foi tirada mas, para evitar que o leitor se confunda, o ideal seria que essas informações estivessem na própria pergunta, no campo "Mais informações sobre a pergunta:".

2. Seria interessante passar a linha de código em que é feita a entrada do número n ("n = int(input('Entre o valor de n: ')") para dentro de "if __name__ == '__main__':", ao invés de deixá-la junto com a definição de funções e métodos.

3. Creio que na hora de copiar o código para o Prorum ficou faltando fechar os parênteses do argumento da função em "print(func1(n)", no primeiro trecho do código que você usou na sua resposta.

4. Você cita o tempo de execução com o método recursivo, usando n=800000. Confesso que não consegui replicar o resultado, por atingir a "maximum recursion depth". Mesmo importando a biblioteca sys e alterando o limite de recursões, não consegui chegar perto desse número (comandos: import sys // sys.setrecursionlimit(novo limite)). Caso tenha feito algum comando adicional, seria interessante colocar na solução (na minha máquina, o limite default de recursões no Python é de 3000).

Um abraço!
...