使这个带有记忆的递归斐波那契更快？

Question

有没有办法让这个程序运行更快？它已经比我尝试制作的 HashMap 版本快，但根据我提交它的位置，它在 45 标记附近仍然太慢。我可以做任何修改来改进它吗？

import java.util.Scanner;

public class Fibo {
    static long[] cache;
    static long ans;

    public static long fibo(int n) {
        if (n == 0) 
            return 1;
        if (n < 2) 
            ans = 1;
        else
            ans = fibo(n - 1) + fibo(n - 2);
        cache[n - 1] = ans;
        return ans;

    }

    public static void main(String[] args) {
            Scanner input = new Scanner(System.in);
            System.out.println("test");
            int num = input.nextInt();
            input.close();
            cache = new long[num];
            long ans = fibo(num);
            System.out.println(ans);
    }
}

Answer 1

您正试图在缓存中记住答案，但您没有使用它。在任何其他计算之前检查您的缓存。此外，当您达到 fibo(0) 时，您会得到一个 ArrayIndexOutOfBoundsException，因为您要减去一个。删除减法并增加数组的大小以解决它。

public static long fibo(int n) {
    // Try cache first.
    if (cache[n] != 0) return cache[n];
    if (n == 0) 
        return 1;
    if (n < 2) 
        ans = 1;
    else
        ans = fibo(n - 1) + fibo(n - 2);
    // Don't subtract one.
    cache[n] = ans;
    return ans;
}

主要是为 fibo(num) 的答案留出空间。

cache = new long[num + 1];

Answer 2

您可以通过实际使用缓存值来使其更快：

public static long fibo(int n) {
    if (cache[n] > 0) {
        return cache[n];
    }
    ...
    cache[n] = ans; // you are saving at the wrong index
    ...
}

尽管使用记忆化的时间复杂度为 "fast"，时间复杂度为 O(n)，但有一个数学复杂度 O(log n) 的解决方案速度超快。

使这个带有记忆的递归斐波那契更快？

Making this recursive fibonacci with memoization even faster?

java

recursion

memoization

fibonacci