[resolvido] cálculo da função f(x) = x + f(x-1)

Assuntos Gerais
#1

Alguém sabe se existe um algoritmo O© para calcular a função f(0) = 0 , f(x) = x + f(x-1) , para x > 0 ?

#2

voce quer calcular o valor da fç em um ponto ou tracar o grafico para um intervalo? o intervalo seria de zero ate infinito?

#3

Sou iniciante em programação, mas, se entendi direito, não é só fazer recursivo?

#4

é o mesmo que um fatorial só que com soma:

f(4) = 4 + 3 + 2 + 1 + 0
f(2) = 2 + 1 + 0

O © {
if (c == 0)
return 0;
else
return c + O(c-1);
}

#5

Se esse O© for referente a métrica de desempenho, acho que utilizar recursividade + array (para evitar retrabalho) é a forma mais eficiente que eu conheço para esses tipos de cálculo…

#6

A análise de algoritmos é o coração da ciência da computação. Com ela é possível simplificar um problema até chegar a forma ótima baseada nos custos da execução do programa.

Lembrando que analise de algoritmos não tem nada haver com análise de sistemas. A primeira é o estudo de como otimizar algoritmos.
Aqui tem um artigo muito bom.

#7

Obrigado pessoal, felizmente um amigo meu achou a resposta!

Quando eu falei sobre O© eu estava sim falando sobre a complexidade. Tanto a solução recursiva quanto a iterativa para esse cálculo tem complexidade O(n), ou seja, de tempo linear, levando em conta a operação de soma. Felizmente, essa função pode ser calculada como S(n) = (n^2 + n) / 2 e assim obtemos uma solução O©, de tempo constante para qualquer n. É isso aí. Quando tiver um pouco mais de tempo eu posto a demonstração.

#8

Ah, viajei legalz… ainda não conheço muito dessa notação do Ozão [big O]

E realmente uma solução de complexidade constante é uma simplificação algébrica hehe (tanto tempo sem exercitar isso que é pouco provável que eu chegasse a resposta certa sozinho)…

Agente vai ficando meio “bitolado” colocando algorítmo pra tudo, mesmo quando existem formas bem mais performáticas xD,

#9

Não tinha nem me tocado no O©.

Da maneira como o DavidUser desenvolveu a equação, deu para perceber claramente que era a soma de uma PA de razão r = 1. Dado isso, era só pegar a equação da soma dos n primeiros termos de uma PA e fazer as modificações necessárias.

#10