fibonacci 的三种实现方法的耗费时间

fibonacci.js

/*
 * 1 , 1 , 2 , 3 , 5 , 8 , 13 , 21 , 34 , 55 , 89 , 144
 */

function fibonacci(n) {
    if (n < 2) return 1

    return fibonacci(n-1) + fibonacci(n-2)
}

function fibonacci2(n) {
    let first = 0
    let second = 1
    let temp

    while(n--) {
        // [first, second] = [second, first+second]
        temp = second
        second += first
        first = temp
    }
    return second
}

function fibonacci3(n) {
    let first = 0
    let second = 1

    while(n--) {
        [first, second] = [second, first+second]
    }
    return second
}

function fibonacci4(n, memo) {
    memo = memo || {}

    if (n < 2) return 1
    if (memo[n]) return memo[n]

    return memo[n] = fibonacci3(n-1, memo) + fibonacci3(n-2, memo)
}

const { performance} = require('perf_hooks')

let len = 100000
let num = 15
let ret, ret2, ret3, ret4

let t1 = performance.now()
for (var i = 0; i < len; i++) {
    ret = fibonacci(num)
}
let t2 = performance.now()
for (var i = 0; i < len; i++) {
    ret2 = fibonacci2(num)
}
let t3 = performance.now()
for (var i = 0; i < len; i++) {
    ret3 = fibonacci3(num)
}
let t4 = performance.now()
for (var i = 0; i < len; i++) {
    ret = fibonacci4(num)
}
let t5 = performance.now()

console.log('fibonacci:', t2 - t1)
console.log('fibonacci2:', t3 - t2)
console.log('fibonacci3:', t4 - t3)
console.log('fibonacci4:', t5 - t4)