Complexidade De Algorítmos

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.