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

GUJ Master Membro desde: 29/05/2008 14:09:28 Mensagens: 1617 Online

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

Java Ninja Membro desde: 30/07/2005 12:42:29 Mensagens: 262 Offline

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

Debugger Membro desde: 29/03/2010 19:22:50 Mensagens: 51 Offline

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

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

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

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

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

Se esse O(c) 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...

GUJ Expert Membro desde: 13/11/2008 12:10:18 Mensagens: 3927 Offline

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.

http://en.wikipedia.org/wiki/Analysis_of_algorithms

GUJ Master Membro desde: 29/05/2008 14:09:28 Mensagens: 1617 Online

Obrigado pessoal, felizmente um amigo meu achou a resposta!

Quando eu falei sobre O(c) 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(c), de tempo constante para qualquer n. É isso aí. Quando tiver um pouco mais de tempo eu posto a demonstração.

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,

Debugger Membro desde: 29/03/2010 19:22:50 Mensagens: 51 Offline

Não tinha nem me tocado no O(c).

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.

Notícias, artigos e o maior fórum brasileiro sobre Java