使用递归查找斐波那契数列中的数字 - 如何使其更快？

Question

我的查找斐波那契数列中的数字的代码工作正常，但它真的很慢。（几乎不可能找到超过 n=55 的数字）。我哪里弄错了？

public static void main(String[] args) {

    for (; ; ) {
        System.out.println("The value of the fibonacci sequence ");
        Scanner numer = new Scanner(System.in);
        long n = numer.nextLong();
        long result = Fib(n);
        System.out.println(result);

    }
}


private static long Fib(long n) {
    if (n <= 0) { System.out.println("Error"); return 0;}
    else if (n == 1 | n == 2) return 1;
    else return Fib(n-1)+ Fib(n-2) ;

}

Answer 1

你知道你为每个 k 计算了多少次 fib(k) 吗？如果你想让你的程序运行快，不要那么盲目地使用递归，而是使用循环：

private static long Fib(long n) {
    long prev = 1;
    long current = 1;
    if (n <= 0) { System.out.println("Error"); return 0;}
    if (n == 1 | n == 2) return 1;
    for (int i = 3; i <= n; i++) {
        long next = prev + current;
        prev = current;
        current = next;
    }
    return current;

}

如果你只想通过递归来解决这个问题，那么你需要存储已经计算的结果。它可以通过记忆或使用惰性动态编程来完成，而且它比只使用循环要难得多。

Answer 2

即使@Jason 提出了改进建议，这仍然是一个 指数时间 复杂度为 O(2^N) 的算法。

为了将时间复杂度降低到O(N)，也称为线性时间，我提出了以下方法（称为“memoization "，因为我们保存了我们计算的每个值，并在每次被询问时直接 return 它 O(1) 时间，因此堆栈帧将少得多，并且最多会随着 [=26= 的值线性增加]).

public static void main(String[] args) {
    // receive customer input
    HashMap<Long, Long> map = new HashMap<>();
    long result = Fib(n, map);
}

private long Fib(long n, HashMap<Long, Long> map) {
    if (n <= 0) {
        return 0;
    }
    if (n == 1) {
        return 1;
    }
    if (map.containsKey(n)) {
        return map.get(n);
    } else {
        map.put(n, Fib(n - 1, map) + Fib(n - 2, map));
        return map.get(n);
    }

}

您可以通过在 Leetcode 的斐波那契练习中提交它们来比较这两个解决方案。

此外，上面 link 中的 "Solution" 选项卡下解释了这两种方法（您的方法和我的类似的记忆方法），您可以在其中了解有关时间复杂度的更多信息。

使用递归查找斐波那契数列中的数字 - 如何使其更快？

Finding the numbers in the Fibonacci sequence using recursion - how to make it faster?

java

recursion

fibonacci