递归和迭代的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;
}

这是最有效的吗？什么是大订单？

我还被要求给出递归实现的大概念:

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))除非使用了memoization或类似的,否则递归定义.

Fibonacci数也有一个Closed形式表达式,这个链接有一些更快的fib函数的实现.