使斐波那契更快

Question

我被要求写一个简单的Fibonacci算法实现,然后让它更快.

这是我的初步实施

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()来计算计算Fibonacci时经过的时间.

正如您在下图所示,这种实现方式迅速呈指数级增长

所以我有一个简单的优化想法.要将先前的值放在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)处得到了长的溢出(给我F(104)= -7076989329685730859,这是错误的).我发现它太快了**我想知道我的代码中是否有任何错误(谢谢你的检查,请告诉我)**.请看第二张图片:

我的更快的斐波纳契算法的实现是否正确(似乎对我来说因为它获得的值与第一个版本相同,但由于第一个版本太慢,我无法使用它来计算更大的值,如F(75))？还有什么方法可以让它更快？还是有更好的方法让它更快？另外,如何计算Fibonacci以获得更大的值(例如150,200)而不会出现**长溢出**？虽然看起来很快,但我想把它推到极限.我记得Abrash先生说' 最好的优化者是你的双耳之间 ',所以我相信它仍然可以改进.谢谢你的帮忙

[版本注意:]虽然这个问题解决了我的问题中的一个主要问题,但你可以从上面看到我有其他问题.

Answer 1

动态编程

想法:不是多次重新计算相同的值,而是只存储计算的值并随着它一起使用它们.

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吧.A [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.

IDEA

动态编程(通常称为DP)是解决特定类问题的非常强大的技术.它要求非常优雅的方法和简单的思维,编码部分非常容易.这个想法非常简单,如果你已经解决了给定输入的问题,那么保存结果以供将来参考,以避免再次解决同样的问题.很快"记住你的过去".

如果给定的问题可以分解为较小的子问题,并且这些较小的子问题又被分成仍然较小的子问题,并且在这个过程中,如果你观察到一些over-lappping subproblems,那么它对DP来说是一个很大的提示.此外,子问题的最优解决方案有助于给定问题的最优解(称为Optimal Substructure Property).

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

1.)自上而下:通过分解来开始解决给定的问题.如果您发现问题已经解决,那么只需返回已保存的答案.如果尚未解决,请解决并保存答案.这通常很容易想到并且非常直观.这被称为Memoization.(我用过这个想法).

2.)自下而上:分析问题并查看子问题的解决顺序,并从琐碎的子问题开始解决问题.在此过程中,保证在解决问题之前解决子问题.这称为动态编程.(MinecraftShamrock用过这个主意)

还有更多!

(其他方法)

看看我们寻求更好的解决方案并不止于此.你会看到一种不同的方法 -

如果您知道如何解决,recurrence relation那么您将找到这种关系的解决方案

f(n)=f(n-1)+f(n-2) given 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)操作中获得数字.你必须通过平方来学习指数.

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

Answer 2

如果你需要经常计算第n个斐波纳契数,我建议使用amalsom的答案.

但是如果你想计算一个非常大的斐波纳契数,你就会因为存储所有较小的斐波纳契数而耗尽内存.以下伪代码仅将最后两个斐波纳契数保存在内存中,即它需要的内存要少得多:

fibonacci(n) {
    if n = 0: return 0;
    if n = 1: return 1;
    a = 0;
    b = 1;
    for i from 2 to n: {
        sum = a + b;
        a = b;
        b = sum;
    }
    return b;
}

分析
这可以计算非常高的斐波纳契数,内存消耗非常低:循环重复n-1次,我们有O(n)时间.空间复杂性也很有趣:第n个斐波纳契数的长度为O(n),可以很容易地显示出来:F _n <= 2*F _n-1 这意味着第n个斐波那契数最多是两倍大作为其前身.将二进制数加倍等于单个左移,这将所需位数增加一.因此,表示第n个斐波纳契数最多占用O(n)空间.我们在存储器中最多有三个连续的斐波纳契数,这使得O(n)+ O(n-1)+ O(n-2)= O(n)总空间消耗.与此相反,memoization算法始终将前n个fibonacci数保存在内存中,这使得O(n)+ O(n-1)+ O(n-2)+ ... + O(1)= O(n ^ 2)空间消耗.

那么应该使用哪种方式？
将所有较低的斐波纳契数保留在记忆中的唯一原因是,如果您经常需要斐波纳契数.这是一个平衡时间和内存消耗的问题.

Answer 3

远离Fibonacci递归并使用身份

(F(2n), F(2n-1)) = (F(n)^2 + 2 F(n) F(n-1), F(n)^2+F(n-1)^2)
(F(2n+1), F(2n)) = (F(n+1)^2+F(n)^2, 2 F(n+1) F(n) - F(n)^2)

这允许您以(F(k + 1),F(k))计算(F(m + 1),F(m))k为m的一半大小.迭代写入一些位移除除2,这应该通过平方同时保持完整的整数运算,给你理论O(log n)求幂速度.(好吧,O(log n)算术运算.由于你将使用大约n位的数字,一旦你被迫切换到一个大的整数库,它就不会是O(log n)时间.在F(50之后) ),您将溢出整数数据类型,该类型最多只能达到2 ^(31).)

(抱歉不能很好地记住Java,以便在Java中实现这一点;任何想要的人都可以自由编辑它.)

Answer 4

• 斐波那契(0)= 0
• 斐波那契(1)= 1
• Fibonacci(n)= Fibonacci(n - 1)+ Fibonacci(n - 2),当n> = 2时

通常有两种计算斐波那契数的方法:

1. 递归:

   public long getFibonacci(long n) {
     if(n <= 1) {
       return n;
     } else {
       return getFibonacci(n - 1) + getFibonacci(n - 2);
     }
   }
   

   这种方式直观且易于理解,而由于它不重用计算的斐波纳契数,时间复杂度大约是O(2^n),但它不存储计算结果,因此它节省了很多空间,实际上空间复杂度也是如此O(1).

2. 动态编程:

   public long getFibonacci(long n) {
     long[] f = new long[(int)(n + 1)];
     f[0] = 0;
     f[1] = 1;
     for(int i=2;i<=n;i++) {
       f[i] = f[i - 1] + f[i - 2];
     }
     return f[(int)n];
   }
   

   这种Memoization方法计算Fibonacci数,并在计算下一个时重用它们.时间复杂度非常好,即O(n)空间复杂度O(n).让我们来研究是否可以优化空间复杂度......因为f(i)只需要f(i - 1)和f(i - 2),所以没有必要存储所有计算出的斐波纳契数.

   更有效的实施是:

   public long getFibonacci(long n) {
     if(n <= 1) {
       return n;
     }
     long x = 0, y = 1;
     long ans;
     for(int i=2;i<=n;i++) {
       ans = x + y;
       x = y;
       y = ans;
     }
     return ans;
   }
   

   随着时间的复杂性O(n)和空间的复杂性O(1).

补充:由于斐波那契数量增长速度惊人,long只能处理少于100个斐波纳契数.在Java中,我们可以使用BigInteger存储更多Fibonacci数字.

Answer 5

预先计算大量fib(n)结果,并将它们作为查找表存储在算法中.巴姆,免费"速度"

现在,如果您需要计算fib(101)并且已经存储了0到100的fib,这就像尝试计算一样fib(1).

这可能不是这个功课所要求的,但它是一个完全合法的策略,基本上缓存的想法远离运行算法.如果你知道你可能经常计算前100个纤维并且你需要真的非常快,那就没有比O(1)快的速度了.因此,完全在带外计算这些值并存储它们,以便以后查找它们.

当然,在计算它们时也会缓存值:)重复计算是浪费.

Answer 6

这里使用迭代方法而不是递归来剪切代码.

输出示例:

Enter n: 5
F(5) = 5 ... computed in 1 milliseconds
Enter n: 50
F(50) = 12586269025 ... computed in 0 milliseconds
Enter n: 500
F(500) = ...4125 ... computed in 2 milliseconds
Enter n: 500
F(500) = ...4125 ... computed in 0 milliseconds
Enter n: 500000
F(500000) = ...453125 ... computed in 5,718 milliseconds
Enter n: 500000
F(500000) = ...453125 ... computed in 0 milliseconds

...为了更好的视图,省略了一些结果.

代码段:

public class CachedFibonacci {
    private static Map<BigDecimal, BigDecimal> previousValuesHolder;
    static {
        previousValuesHolder = new HashMap<>();
        previousValuesHolder.put(BigDecimal.ZERO, BigDecimal.ZERO);
        previousValuesHolder.put(BigDecimal.ONE, BigDecimal.ONE);
    }

    public static BigDecimal getFibonacciOf(long number) {
        if (0 == number) {
            return BigDecimal.ZERO;
        } else if (1 == number) {
            return BigDecimal.ONE;
        } else {
            if (previousValuesHolder.containsKey(BigDecimal.valueOf(number))) {
                return previousValuesHolder.get(BigDecimal.valueOf(number));
            } else {
                BigDecimal olderValue = BigDecimal.ONE,
                        oldValue = BigDecimal.ONE,
                        newValue = BigDecimal.ONE;

                for (int i = 3; i <= number; i++) {
                    newValue = oldValue.add(olderValue);
                    olderValue = oldValue;
                    oldValue = newValue;
                }
                previousValuesHolder.put(BigDecimal.valueOf(number), newValue);
                return newValue;
            }
        }
    }

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

                System.out.printf("F(%d) = %.0f ... computed in %,d milliseconds\n", inputNumber, fibo, delta);
            } else {
                System.err.println("You must enter number > 0");
                System.out.println("try, enter number again, please:");
                break;
            }
        }
    }
}

这种方法比递归版本运行得快得多.

在这种情况下,迭代解决方案往往会更快一些,因为每个递归方法调用都需要一定的处理器时间.原则上,如果智能编译器遵循简单模式,则可以避免递归方法调用,但大多数编译器不这样做.从这个角度来看,迭代解决方案是更可取的.