javascript算法集：数组中最大差值｜斐波那契数列
数组中最大差值
方法一
1 2 3 | function getMaxProfit1(ary){ return Math.max.apply(null, ary) - Math.min.apply(null, ary); } |
测试：getMaxProfit1([1, 2, 3, 4]) // 3
斐波那契数列
这里我们只实现通项公式
斐波那契数列 方法一
1 2 3 4 5 6 7 | function fib1(n){ if(n === 1 || n === 2){ return 1; } return fib1(n - 1) + fib1(n - 2); } |
PS：时间复杂度为O(2^n)，空间复杂度为O(n)
斐波那契数列 方法二
1 2 3 4 5 6 7 8 9 10 11 12 13 | function fib2(n){ let tem = [1, 1]; if(n === 1 || n === 2){ return 1; } // 数组索引从0开始，数列索引从1开始 for(let i = 2; i < n; i++){ tem[i] = tem[i-1] + tem[i-2]; } return tem[n-1]; } |
PS：时间复杂度为O(n)，空间复杂度为O(n)
斐波那契数列 方法三
1 2 3 4 5 6 7 8 9 10 11 12 | function fib2(n){ let prev = 1, next = 1, res; for(let i = 2; i < n; i++){ res = prev + next; prev = next; next = res; } return res; } |
PS：时间复杂度为O(n)，空间复杂度为O(1)
测试：fib2(3) // 2
THE END
