<分区>
所以，我在 Java 中有一个递归方法来获取第 n 个斐波那契数 - 我唯一的问题是:时间复杂度是多少？我认为是 O(2^n)，但我可能弄错了？ (我知道迭代更好，但这是一种练习)
public int fibonacciRecursive(int n)
{
if(n == 1 || n == 2) return 1;
else return fibonacciRecursive(n-2) + fibonacciRecursive(n-1);
}
<分区>
所以，我在 Java 中有一个递归方法来获取第 n 个斐波那契数 - 我唯一的问题是:时间复杂度是多少？我认为是 O(2^n)，但我可能弄错了？ (我知道迭代更好，但这是一种练习)
public int fibonacciRecursive(int n)
{
if(n == 1 || n == 2) return 1;
else return fibonacciRecursive(n-2) + fibonacciRecursive(n-1);
}
最佳答案
您的递归代码具有指数运行时间。但是我觉得底数不是2，大概是黄金比例(1.62左右)。但当然 O(1.62^n) 也自动为 O(2^n)。
可以递归计算运行时间:
t(1)=1
t(2)=1
t(n)=t(n-1)+t(n-2)+1
这与斐波那契数本身的递归定义非常相似。递归方程中的 +1 可能与大 n 无关。 S 我相信它的增长速度与斐波那契数大致相同，并且以黄金比例为基础呈指数增长。
您可以使用记忆化来加快速度，即缓存已经计算出的结果。然后它与迭代版本一样具有 O(n) 运行时间。
您的迭代代码的运行时间为 O(n)
您有一个简单的循环，其中包含 O(n) 步并且每次迭代的时间恒定。
关于java - 斐波那契算法的时间复杂度，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/4768781/