TrabalhosGratuitos.com - Trabalhos, Monografias, Artigos, Exames, Resumos de livros, Dissertações
Pesquisar

Complexidade De Algorítmos

Resenha: Complexidade De Algorítmos. Pesquise 859.000+ trabalhos acadêmicos

Por:   •  12/10/2014  •  Resenha  •  225 Palavras (1 Páginas)  •  299 Visualizações

1) Implementar o algoritmo Fibonacci como uma função em C:

a) Algoritmo recursivo

int FibR

(int n, int a, int b) {

if

(n == 0)

return a;

if (n ==1)

return b;

return FibR (n-1, b, a+b);

}

Int Fib (intn) {

return FibR (n, 0, 1);

}

b) Algoritmo não recursivo

int FibIter(int n) {

int i, k, F;

i = 1; F = 0;

for (k = 1; k <= n; k++) {

F += i;

i = F - i;

}

return F;

}

2) Comparar as complexidades destes dois algoritmos e mostrar qual é mais eficiente e justificar a sua resposta

Comparação dos Algoritmos:

A:

• Duas chamadas recursivas

• Cada uma resolvendo a metade do problema

• Muito usado na prática

• Solução eficiente de problemas

• Decomposição

B:

• Complexidade: O(n)

• Conclusão: não usar recursividade cegamente!

• Porções diferentes do problema

Como aprendemos em sala de aula, nem sempre os algoritmos criados usando números exponenciais são as melhores opções. À primeira vista o algoritmo pode até ser menor e mais “limpo” quando usamos números exponenciais mas na prática pode ser que este algoritmo demore mais para executar os processos do que os algoritmos mais simples mas que são mais extensos.

Recursividade vale a pena para Algoritmos complexos, cuja a implementação iterativa é complexa e normalmente requer o uso explícito de uma pilha, assim seria mais útil utilizar o algoritmo não recursivo para resolver Este problema que é bem simples, e não necessita de algo tão complexos como a recursividade.

...

Disponível apenas no TrabalhosGratuitos.com