Complexité des temps de fonctionnement LAB et des nombres de fibonacci (java)

Question

ont regardé la page et beaucoup de gens formidables aidant dehors ainsi j'ai une tâche de laboratoire et je sais que je dois faire une méthode concernant les nombres de fibonacci pour calculer le nombre dans le position n, mais je ne suis pas tout à fait sûr de ce que mettre à l'intérieur de la méthode que je connais est ce que je dois penser à l'espoir que vous pouvez donner et idée. Avoir des problèmes (ne pas demander de faire le hw pour moi ok) Merci.

1. nombres de Fibonacci et la complexité

nombres de Fibonacci sont définis récursivement comme suit:
F (n) = n, pour n < = 1
F (n) = F (n-1) + F (n-2) pour n> 1
Ecrire les méthodes suivantes pour calculer F (n): méthode
a) AO (2n^n) sur la base de la définition récursive
b) du procédé AO (n) qui utilise une boucle
c) Une méthode O (1) qui utilise la solution à forme fermée - n'hésitez pas à chercher cette formule en ligne.

Testez les trois méthodes en utilisant n = 10; 20; 50; 100; 1,000; 10 000; 100 000 et 1 000 000 Si un algorithme particulier et une combinaison d'entrées ne renvoient pas de réponse dans un laps de temps raisonnable, notez que dans votre rapport (c'est-à-dire, n'attendez pas des heures (ou pire) pour que votre programme se termine).

Answer 1

Je suppose que "Hw" signifie devoir, donc je n'ai pas peur du code.

a) O (2n) et O (n) sont la même chose. Voulez-vous dire O (2^n)? Cela se produira si vous utilisez la méthode récursive sans mettre en cache les résultats. B) C'est la manière «évidente» de l'implémenter, en utilisant une implémentation procédurale et en rappelant les deux derniers nombres et en les utilisant pour calculer la suivante. Dans le pseudo-code ce serait quelque chose comme loop { a, b = b, a+b; }

c) Cela ne fonctionnera pas pour tout n sauf si vous avez une précision infinie, et la précision infinie n'est pas O (1). Par exemple, lorsque j'utilise double fib (73), cela correspond à 806515533049395, mais en réalité c'est 80651553304939 . La différence est due à des erreurs d'arrondi lorsque vous travaillez avec des nombres à virgule flottante. Et en ce qui concerne la solution O (n), si vous calculez jusqu'à fib (1000000), un entier de 64 bits ne sera pas assez proche pour stocker le résultat. Vous devrez utiliser BigIntegers. L'ajout de deux BigIntegers n'est pas une opération O (1), donc la performance O (n) que j'ai mentionnée est trop optimiste.

Answer 2

Eh bien, pour répondre à la partie c il y a une fonction de temps constant qui va calculer le nième nombre de fibonacci. Vous pouvez trouver la formule pour cela ici: http://en.wikipedia.org/wiki/Fibonacci_number#Closed_form_expression