java - 使斐波那契更快

Question

这个问题在这里已经有了答案:

nth fibonacci number in sublinear time (16 个答案)

关闭 7年前。

我被要求编写斐波那契算法的简单实现，然后让它更快。

这是我最初的实现

public class Fibonacci {

    public static long getFibonacciOf(long n) {
        if (n== 0) {
            return 0;
        } else if (n == 1) {
            return 1;
        } else {
            return getFibonacciOf(n-2) + getFibonacciOf(n-1);
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner (System.in);
        while (true) {
            System.out.println("Enter n :");
            long n = scanner.nextLong();
            if (n >= 0) {
                long beginTime = System.currentTimeMillis();
                long fibo = getFibonacciOf(n);
                long endTime = System.currentTimeMillis();

                long delta = endTime - beginTime;

                System.out.println("F(" + n + ") = " + fibo + " ... computed     in " + delta + " milliseconds");
            } else {
                break;

            }
        }

    }

}

如您所见，我正在使用 System.currentTimeMillis() 来获得计算斐波那契时所用时间的简单度量。

这种实现速度很快，速度却呈指数级增长，如下图所示

所以我有一个简单的优化想法。将以前的值放在 HashMap 中，而不是每次都重新计算它们，如果它们存在，只需从 HashMap 中取回它们。如果它们不存在，我们将它们放入 HashMap 中。

这是新版本的代码

public class FasterFibonacci {

    private static Map<Long, Long> previousValuesHolder;
    static {
        previousValuesHolder = new HashMap<Long, Long>();
        previousValuesHolder.put(Long.valueOf(0), Long.valueOf(0));
        previousValuesHolder.put(Long.valueOf(1), Long.valueOf(1));
    }
    public static long getFibonacciOf(long n) {
        if (n== 0) {

            return 0;
        } else if (n == 1) {
            return 1;
        } else {
            if (previousValuesHolder.containsKey(Long.valueOf(n))) {
                return previousValuesHolder.get(n);
            } {

                long newValue = getFibonacciOf(n-2) + getFibonacciOf(n-1);
                previousValuesHolder.put(Long.valueOf(n),     Long.valueOf(newValue));
                return newValue;
            }

        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner (System.in);
        while (true) {
            System.out.println("Enter n :");
            long n = scanner.nextLong();
            if (n >= 0) {
                long beginTime = System.currentTimeMillis();
                long fibo = getFibonacciOf(n);
                long endTime = System.currentTimeMillis();

                long delta = endTime - beginTime;

                System.out.println("F(" + n + ") = " + fibo + " ... computed     in " + delta + " milliseconds");
            } else {
                break;

            }
        }

    }

这种变化使计算速度极快。我立即计算了从 2 到 103 的所有值，我在 F(104) 处得到 long 溢出(给我 F(104) = -7076989329685730859，这是错误的 )。我发现它太快了**我想知道我的代码中是否有任何错误(感谢您的检查并请告诉我)**。请看第二张图:

我更快的斐波那契算法的实现是否正确(对我来说似乎是因为它获得与第一个版本相同的值，但由于第一个版本太慢我无法用它计算更大的值，例如 F(75) )？我还能用什么其他方法让它更快？或者有没有更好的方法让它更快？另外我如何计算斐波那契以获得更大的值(例如 150、200)而不会出现 **long 溢出**？虽然看起来很快，但我想把它推到极限。我记得 Abrash 先生说过'最好的优化器在你的两只耳朵之间'，所以我相信它仍然可以改进。感谢您的帮助

[版本说明:] 虽然 this问题解决了我的问题的要点之一，您可以从上面看到我还有其他问题。

Answer 1

动态编程

Idea:Instead of recomputing the same value multiple times you just store the value calculated and use them as you go along.

f(n)=f(n-1)+f(n-2) 其中 f(0)=0,f(1)=1。所以当你计算出 f(n-1) 时，如果你存储 f(n) 和 f(n-1) 的值，你可以很容易地计算出 f(n)。

让我们先看一个 Bignums 数组。一个[1..200]。将它们初始化为 -1。

伪代码

fact(n)
{
if(A[n]!=-1) return A[n];
A[0]=0;
A[1]=1;
for i=2 to n
  A[i]= addition of A[i],A[i-1];
return A[n]
}

这在 O(n) 时间内运行。自己检查一下。

这种技术也称为memoization。

理念

动态编程(通常称为 DP)是解决特定类别问题的一种非常强大的技术。它需要非常优雅的方法表述和简单的思维，并且编码部分非常容易。这个想法很简单，如果你用给定的输入解决了一个问题，那么保存结果以备将来引用，以避免再次解决同样的问题..很快'记住你的过去'。

如果给定的问题可以分解成更小的子问题，这些更小的子问题又被分成更小的子问题，在这个过程中，如果你观察到一些 over-lapping 子问题，那么它对 DP 来说是一个很大的提示。此外，子问题的最优解有助于给定问题的最优解(称为Optimal Substructure Property)。

有两种方法可以做到这一点。

1.) Top-Down : Start solving the given problem by breaking it down. If you see that the problem has been solved already, then just return the saved answer. If it has not been solved, solve it and save the answer. This is usually easy to think of and very intuitive. This is referred to as Memoization. (I have used this idea).

2.) Bottom-Up : Analyze the problem and see the order in which the sub-problems are solved and start solving from the trivial subproblem, up towards the given problem. In this process, it is guaranteed that the subproblems are solved before solving the problem. This is referred to as Dynamic Programming. (MinecraftShamrock used this idea)

---

还有更多!

(其他方法)

请注意，我们寻求更好解决方案的努力并没有就此结束。你会看到不同的方法-

If you know how to solve recurrence relation then you will find a solution to this relation

f(n)=f(n-1)+f(n-2) 给定 f(0)=0,f(1)=1

解决后你会得到公式-

f(n)= (1/sqrt(5))((1+sqrt(5))/2)^n - (1/sqrt(5))((1-sqrt(5) )/2)^n

可以写成更紧凑的形式

f(n)=floor((((1+sqrt(5))/2)^n)/sqrt(5) + 1/2)

复杂性

你可以在 O(logn) 运算中得到一个数字。你必须学习Exponentiation by squaring .

编辑:很高兴指出这并不一定意味着可以在 O(logn) 中找到斐波那契数。实际上，我们需要计算的位数是线性的。可能是因为我所说的立场似乎声称一个数字的阶乘可以在 O(logn) 时间内计算的错误想法。[Bakurui，MinecraftShamrock 对此发表评论]