如何使用复杂度为 O(n) 的 Javascript 找到第 n 个斐波那契数

Question

真的很努力想弄清楚如何解决这个问题。问题是使用 javascript.

找到具有 O(n) 复杂度的第 n 个斐波那契数

我找到了很多关于如何使用 C++ 或 Python 解决此问题的精彩文章，但每次我尝试实现相同的逻辑时，我都以 Maximum call stack size exceeded.[=14= 告终]

Python

中的示例代码

MAX = 1000

# Create an array for memoization
f = [0] * MAX

# Returns n'th fuibonacci number using table f[]
def fib(n) :
        # Base cases
        if (n == 0) :
                return 0
        if (n == 1 or n == 2) :
                f[n] = 1
                return (f[n])

        # If fib(n) is already computed
        if (f[n]) :
                return f[n]

        if( n & 1) :
                k = (n + 1) // 2
        else : 
                k = n // 2

        # Applyting above formula [Note value n&1 is 1
        # if n is odd, else 0.
        if((n & 1) ) :
                f[n] = (fib(k) * fib(k) + fib(k-1) * fib(k-1))
        else :
                f[n] = (2*fib(k-1) + fib(k))*fib(k)

        return f[n]


// # Driver code
// n = 9
// print(fib(n))

然后尝试将其移植到 Javascript

const MAX = 1000;
let f = Array(MAX).fill(0);
let k;

const fib = (n) => {

    if (n == 0) {
        return 0;
    }

    if (n == 1 || n == 2) {
        f[n] = 1;

        return f[n]
    }

    if (f[n]) {
        return f[n]
    }

    if (n & 1) {
        k = Math.floor(((n + 1) / 2))
    } else {
        k = Math.floor(n / 2)
    }

    if ((n & 1)) {
        f[n] = (fib(k) * fib(k) + fib(k-1) * fib(k-1))
    } else {
        f[n] = (2*fib(k-1) + fib(k))*fib(k)
    }

    return f[n]
}

console.log(fib(9))

这显然行不通。在 Javascript 中，这以无限循环结束。那么你如何使用 Javascript?

来解决这个问题？

提前致谢

Answer 1

您可以从下到上迭代（如尾递归）：

var fib_tail = function(n){
        if(n == 0)
             return 0;
        if(n == 1 || n == 2)
             return 1;
        var prev_1 = 1, prev_2 = 1, current; 
        // O(n)
        for(var i = 3; i <= n; i++)
        {
            current = prev_1 + prev_2;
            prev_1 = prev_2;
            prev_2 = current;
        }
        return current;
 }
 console.log(fib_tail(1000))

Answer 2

只需使用两个变量和一个对提供的数字进行倒计时的循环。

function fib(n){
    let [a, b] = [0, 1];
    while (--n > 0) {
      [a, b] = [b, a+b];
    }
    return b;
}

console.log(fib(10));

Answer 3

问题与 k 变量的范围有关。它必须在函数内部：

const fib = (n) => {
    let k;

您可以在这里找到更多好的实现 list

DEMO

Answer 4

这里有一个更简单的方法，使用迭代或递归方法：

function FibSmartRecursive(n, a = 0, b = 1) {
    return n > 1 ? FibSmartRecursive(n-1, b, a+b) : a;
}

function FibIterative(n) {
    if (n < 2) 
        return n;

    var a = 0, b = 1, c = 1;

    while (--n > 1) {
        a = b;
        b = c;
        c = a + b;
    }

    return c;
}

function FibMemoization(n, seenIt = {}) {//could use [] as well here
    if (n < 2) 
        return n;
    if (seenIt[n]) 
        return seenIt[n];

    return seenIt[n] = FibMemoization(n-1, seenIt) + FibMemoization(n-2, seenIt); 
}

console.log(FibMemoization(25)); //75025
console.log(FibIterative(25)); //75025
console.log(FibSmartRecursive(25)); //75025

Answer 5

斐波那契数 O(n) 时间和 O(1) space 复杂度：

function fib(n) {
    let prev = 0, next =1;
    if(n < 0)
        throw 'not a valid value';
    if(n === prev || n === next)
        return n;
    while(n >= 2) {
        [prev, next] = [next, prev+next];
        n--;
    }
    return next;
}

Answer 6

你可以不用递归使用循环来解决这个问题，运行时 O(n):

function nthFibo(n) {
    // Return the n-th number in the Fibonacci Sequence
    const fibSeq = [0, 1]
    if (n < 3) return seq[n - 1]
    let i = 1
    while (i < n - 1) {
        seq.push(seq[i - 1] + seq[i])
        i += 1
    }
    return seq.slice(-1)[0]
}

如何使用复杂度为 O(n) 的 Javascript 找到第 n 个斐波那契数

How to find nth Fibonacci number using Javascript with O(n) complexity

javascript

python

algorithm

fibonacci

time-complexity