java - 递归和迭代 fib 函数的大顺序？

Question

我被要求以最有效的方式编写一个 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，这就是它效率低下的原因。

Answer 1

您的实现是 O(n)，并且是实现 Fibonacci 函数的正常方式。递归定义是 O(fib(n)) 除非使用内存或类似方法。

还有一个Closed form expression斐波那契数列，以及 This link有一些更快的 fib 函数的实现。