哪个斐波纳契函数的评估速度会更快？

我想获得第一个100斐波那契数字输出到.txt文件。 我得到它运行，但它需要一段时间。 Fibonacci或Fibonacci2会更快吗？ 下面的代码使用第一个。

#!/usr/bin/env node var fs = require('fs'); // Fibonacci // http://en.wikipedia.org/wiki/Fibonacci_number var fibonacci = function(n) { if(n < 1) { return 0;} else if(n == 1 || n == 2) { return 1;} else if(n > 2) { return fibonacci(n - 1) + fibonacci(n - 2);} }; // Fibonacci: closed form expression // http://en.wikipedia.org/wiki/Golden_ratio#Relationship_to_Fibonacci_sequence var fibonacci2 = function(n) { var phi = (1 + Math.sqrt(5))/2; return Math.round((Math.pow(phi, n) - Math.pow(1-phi, n))/Math.sqrt(5)); }; // Find first K Fibonacci numbers via basic for loop var firstkfib = function(k) { var i = 1; var arr = []; for(i = 1; i < k+1; i++) { var fibi = fibonacci(i); arr.push(fibi); // Print to console so I can monitor progress console.log(i + " : " + fibi); } return arr; }; var fmt = function(arr) { return arr.join(","); }; var k = 100; // write to file var outfile = "fibonacci.txt"; var out = fmt(firstkfib(k)); fs.writeFileSync(outfile, out); console.log("\nScript: " + __filename + "\nWrote: " + out + "\nTo: " + outfile); 

Answer 1

一般来说，recursion函数“更简洁”和“更容易”编写，但往往需要更多的资源（主要是由于堆栈的堆积造成的内存）。 在你的情况下，首先得到100的最好方法是编程使用一个简单的循环，将计算下一个斐波那契数列，并将其添加到列表中。

 double a[100]; a[0] = 1; a[1] = 1; K=2; Do{ { a[k] = a[k - 2] + a[k- 1]; k++; }While (k!=100) 

Answer 2

recursion斐波那契函数是以错误的方式实现的。 recursion实现它的正确方法在本文中讨论recursion和斐波那契数列 。 对于那些懒得阅读，这里是他们的代码（它是在C中，但它不应该太难翻译）：

 unsigned long fib(unsigned int n) { return n == 0 ? 0 : fib2(n, 0, 1); } unsigned long fib2(unsigned int n, unsigned long p0, unsigned long p1) { return n == 1 ? p1 : fib2(n - 1, p1, p0 + p1); } 

更有效的实现会caching斐波那契数列在计算值时的值：

 var cache = []; var fibonacci = function(n) { if(cache.length > n) return cache[n]; return (cache[n] = fib2(n, 0, 1)); }; var fib2 = function(n, p0, p1) { if(cache.length > n) return cache[n]; return n == 1 ? p1 : (cache[n] = fib2(n - 1, p1, p0 + p1)); }; 

我不太了解这个语言，所以代码可能会有一些问题，但这至less是它的要点。

Answer 3

对于你的问题，我们不能比O（n）做得更好，因为你需要产生所有的前n（n = 100）数字。

有趣的是，如果你只需要第n个fib数，那么也存在一个O（log n）解。

该algorithm足够简单：使用“分而治之”的方法findmatrixA的n次幂，并报告第（0,0）个元素，其中

  A = |1 1 | |1 0 | 

recursion正在

  A^n = A^(n/2) * A^(n/2) 

时间复杂度：

 T(n) = T(n/2) + O(1) = O(logn) 

如果你用一张纸来思考，你会发现certificate是简单的，并且基于归纳原理。 如果您仍然需要帮助，请参阅此链接

注意：当然可以迭代计算A，A ^ 2，A ^ 3等等。 然而，与其他答案中描述的其他更简单的解决scheme相比，使用它是没有意义的。 （由于纯粹的代码复杂性）

Answer 4

这是一个非常天真的方式来做这个计算。 尝试做一些事情：

 long[] a = new long[100]; a[0] = 1; a[1] = 1; for (int i = 2; i < 100; ++i) { a[i] = a[i - 2] + a[i - 1]; } for (int i = 0; i < 100; ++i) Console.WriteLine(a[i]); 

这样你得到一个线性时间O（n）