java - 复杂性运行时间 LAB 和斐波那契数 (java)

Question

一直在查看该页面，很多优秀的人在这里提供帮助，所以我有一个实验室作业，我知道我必须做一个关于斐波那契数的方法来计算位置 n 的数字，但我不太确定该怎么做把我知道的方法放进去就是我必须考虑的希望你能给出和想法。遇到麻烦了。(不要要求为我做硬件，好吧)谢谢。

1. 斐波那契数列和复杂性

斐波那契数列的递归定义如下:
F(n) = n，对于 n<=1
F(n) = F(n-1) + F(n-2) 对于 n>1
编写以下方法来计算 F(n):
a) 基于递归定义的 O(2n^n) 方法
b) 使用循环的 O(n) 方法
c) 使用封闭式解的 O(1) 方法 - 请随意在线查找该公式。

使用 n = 10 测试所有三种方法； 20； 50； 100； 1,000； 10,000； 100,000 和 1,000,000。如果特定的算法和输入组合没有在合理的时间内返回答案，请在报告中注明(也就是说，不要等待数小时(或更糟)让程序完成)。

Answer 1

好吧，为了回答c部分，有一个恒定时间函数可以计算第n个斐波那契数。您可以在这里找到它的公式:http://en.wikipedia.org/wiki/Fibonacci_number#Closed_form_expression