MO417 - Questão para a prova oral

MO417 - Questão para a prova oral

Número: 2013-036

Enunciado: Considere a seguinte versão do algoritmo para calcular números de Fibonacci:

FIBONACCI(n)
1 Criar arranjo Fib[1..n]
2 for i=1 to n
3    do Fib[i]=-1
4 Fib[1]=1
5 Fib[2]=1
6 return LOOKUP-FIB(Fib,n)

LOOKUP-FIB(Fib,n)
1 if (Fib[n]>0)
2   then return Fib[n]
3   else
4       return Fib[n]=LOOKUP-FIB(Fib,n-1) + LOOKUP-FIB(Fib,n-2)

Podemos AFIRMAR que:

a) Trata-se um algoritmo memoizado com tempo de execução O(n)
b) Não é um algoritmo memoizado mas seu tempo de execução é O(lg n)
c) Somente é um algoritmo recursivo com tempo de execução O(2^n)
d) É um algoritmo memoizado com tempo de execução O (lg n)
e) NDA

Ideia original de: Marleny Luque Carbajal