我被要求以最有效的方式编写一个 fib 函数?
这是我提供的实现:
public static int fib(int n)
{
int prev1 = 1, prev2 = 1, ans = 1, i = 3;
while (i <= n)
{
ans = prev1 + prev2;
prev1 = prev2;
prev2 = ans;
i++;
}
return ans;
}
这是最有效的吗?什么是大订单?
我还被要求给出递归实现的大 O 符号:
public static int recursiveFib(int n)
{
if (n <= 2)
return 1;
else
return recursiveFib(n-1) + recursiveFib(n - 2);
}
我认为这是指数 2^n,这就是它效率低下的原因。
最佳答案
您的实现是 O(n)
,并且是实现 Fibonacci 函数的正常方式。递归定义是 O(fib(n))
除非使用内存或类似方法。
还有一个Closed form expression斐波那契数列,以及 This link有一些更快的 fib 函数的实现。
关于java - 递归和迭代 fib 函数的大顺序?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/5958221/