fibonacci 数列算是不管哪个语言里头都能碰到的一个问题,其过于经典,导致其有很多解法,大体上可以归为遍历,递归,优化的递归,矩阵(矩阵这个确实很厉害)。

什么是 斐波那契数列? 0,1,1,2,3,5,8 … 除了12以外,剩下的数都满足 f(n) = f(n-2)+f(n-1)

递归方式:

1
2
3
4
5
6
7
8
9
// 递归的方式 - 时间复杂度 O(2^n)
func fibonacciRecusive(num int) int {

if num == 1 || num == 2 {
return 1
}

return fibonacciRecusive(num-1) + fibonacciRecusive(num-2)
}

改进递归方式:

使用map保存计算结果,相当于对已经计算过的数,避免计算第二次。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 时间复杂度 O(n)
var resultMap = make(map[int]int)

func fibonacciRecusiveMem(num int) int {
if val, ok := resultMap[num]; ok {
return val
}

if num == 1 || num == 2 {
return 1
}

result := fibonacciRecusive(num-1) + fibonacciRecusive(num-2)
resultMap[num] = result
return result
}

遍历的方式:

1
2
3
4
5
6
7
8
9
10
11
12
// 时间复杂度 O(n)
func fibonacciIterative(num int) int {
var f = []int{
0, 1,
}

for i := 2; i <= num; i++ {
f = append(f, f[i-1]+f[i-2])
}

return f[num]
}

还有个矩阵的方式,这个建议直接搜索其他文章,因为光看代码完全不好懂,还是得伴着原理一起下饭。