2

我有以下代码：

function fib(n) {

  let first=BigInt(0);
  let snd=BigInt(1);
  let currentNumber;
  let countMax=Math.abs(n)+1;
  let counter=2;
  if(n==0){

    return first;
  } 
  else if (n==1||n==-1){

    return snd;
  }
  while(counter<countMax)
  {
        currentNumber=first+snd;
        first=snd;
        snd=currentNumber;
        counter++;
  }
  if((n<0) && (n % 2 ==0))
  {
    return -currentNumber;
  }
  return currentNumber;
}

这将返回给定 (n) 的斐波那契数。

我的问题是我必须提高这段代码的性能。我尝试使用不同的斐波那契公式（指数公式），但我失去了很多精度，因为 phi 数有无限小数，所以我必须截断并且对于大数字我失去了很多精度。

例如，当我执行 fib(200000) 时，我得到了巨大的数字，但代码花费了超过 12000 毫秒。

另一方面，我尝试使用递归，但性能下降。

你能给我一篇文章或线索吗？

感谢和问候。

4

2 回答 2

2

如果您只是将前一个值添加到当前值，然后将旧的当前值用作前一个值，您将获得显着的性能改进。

function fib(n) {
  var current = 1;
  var previous = 0;
  while (--n) {
    var temp = current;
    current += previous;
    previous = temp;
  }
  return current;
}

console.log(fib(1)); // 1
console.log(fib(2)); // 1
console.log(fib(3)); // 2
console.log(fib(4)); // 3
console.log(fib(5)); // 5

您还可以使用父作用域中的数组来存储以前的值，以避免重做相同的计算。

var fibMap = [1, 1];

function fib(n) {
  var current = fibMap[fibMap.length - 1];
  var previous = fibMap[fibMap.length - 2];
  while (fibMap.length < n) {
    var temp = current;
    current += previous;
    previous = temp;
    fibMap.push(current);
  }
  return fibMap[n - 1];
}

console.log(fib(1)); // 1
console.log(fib(2)); // 1
console.log(fib(3)); // 2
console.log(fib(4)); // 3
console.log(fib(5)); // 5

3次获得第1000个数字的基准

于 2019-08-13T08:05:58.287 回答
2

首先，您可以参考这里的答案

Fib(-n) = -Fib(n)

这是您提到的效率不高的递归实现

function fib(n) {
    // This is to handle positive and negative numbers
    var sign = n >= 0 ? 1 : -1;
    n = Math.abs(n);

    // Now the usual Fibonacci function
    if(n < 2)
        return sign*n;
    return sign*(fib(n-1) + fib(n-2));
}

这很简单，我没有解释，因为如果你知道斐波那契数列，你就知道上面的代码做了什么。如您所知，这对于非常大的数字并不好，因为它会一遍又一遍地递归计算相同的东西。但是我们稍后会在我们的方法中使用它。

现在正朝着更好的方法前进。请参阅以下与您的代码类似的代码，只是有点简洁。

function fib(n) {
    if(n == 0)
        return 0;
    var a = 1;
    var b = 1;
    while(n > 2) {
        b = a + b;
        a = b - a;
    }
    // If n is negative then return negative of fib(n)
    return n < 0 ? -1*b : b;
}

当您只想调用此函数几次时，最好使用此代码。但是如果你想经常调用它，那么你最终会多次计算相同的东西。在这里，您应该跟踪已经计算的值。

例如，如果您调用fib(n)它，它将计算n斐波那契数并返回它。下次如果你调用fib(n)它，它将再次计算它并返回结果。如果我们将这个值存储在某个地方并在下次需要时检索它怎么办？

这也将有助于计算大于斐波那契数的n斐波那契数。如何？

假设我们必须计算 fib(n+1)，然后根据定义fib(n+1) = fib(n) + fib(n-1)。因为，我们已经fib(n)计算并存储在某个地方，我们可以使用该存储值。另外，如果我们已经fib(n)计算并存储了，我们已经fib(n-1)计算并存储了。再读一遍。

我们可以通过使用 JavaScript 对象和我们上面使用的相同递归函数来做到这一点（是的，递归的！）。请参阅下面的代码。

// This object will store already calculated values
// This should be in the global scope or atleast the parent scope
var memo = {};

// We know fib(0) = 0, fib(1) = 1, so store it
memo[0] = 0;
memo[1] = 1;

function fib(n) {
    var sign = n >= 0 ? 1 : -1;
    n = Math.abs(n);

    // If we already calculated the value, just use the same
    if(memo[n] !== undefined)
        return sign*memo[n];

    // Else we will calculate it and store it and also return it
    return sign*(memo[n] = fib(n-1) + fib(n-2));
}

// This will calculate fib(2), fib(3), fib(4) and fib(5). 
// Why it does not calculate fib(0) and fib(1) ? 
// Because it's already calculated, goto line 1 of this code snippet
console.log(fib(5)); // 5

// This will not calculate anything 
// Because fib(-5) is -fib(5) and we already calculated fib(5)
console.log(fib(-5)); // -5

// This will also not calculate anything
// Because we already calculated fib(4) while calculating fib(5)
console.log(fib(4)); // 3

// This will calculate only fib(6) and fib(7)
console.log(fib(7)); // 13

尝试一些测试用例。很容易理解为什么这会更快。

现在您知道您可以存储已经计算的值，您可以修改您的解决方案以使用这种方法而不使用递归，因为递归方法将抛出Uncaught RangeError. 我把这个留给你，因为它值得你自己尝试！

该解决方案在编程中使用了一个称为动态编程的概念。你可以参考这里。

于 2019-08-13T09:19:36.630 回答