斐波那契数列
题目：
实现：
递归实现
function feibo (num) {
if(num <= 2){
return 1
}
return feibo(num-1)+feibo(num-2)
}
console.log(feibo(5))
1
2
3
4
5
6
7
8
2
3
4
5
6
7
8
数组优化递归
空间换取时间的运算
let result = []
function feibo (num) {
for(let i=0;i<num;i++){
if(i < 2){
result[i] = 1
}else {
result[i] = result[i-1]+result[i-2]
}
}
return result[num-1]
}
console.log(feibo(5))
1
2
3
4
5
6
7
8
9
10
11
12
13
2
3
4
5
6
7
8
9
10
11
12
13
减少空间复杂度的实现
function feibo (num) {
let n = 1
let m = 2
while (num-- > 2){
let temp = m
m = n+m
n = temp
}
return m
}
let time1 = new Date().getTime()
// console.log(fiber(4))
console.log(feibo(1000))
let timr2 = new Date().getTime()
console.log(timr2-time1);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
解构赋值的实现
function fiber(n) {
if (n < 4) return n + 1
var [f1, f2] = [1, 2]
for (var i = 3; i <= n; i++) {
[f1, f2] = [f2, f1 + f2]
}
return f2
}
let time1 = new Date().getTime()
// console.log(fiber(4))
console.log(fiber(1000))
let timr2 = new Date().getTime()
console.log(timr2-time1);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
2
3
4
5
6
7
8
9
10
11
12
13
14
← 前端算法 贪心算法解决背包问题→