509. 斐波那契数

难度: 简单




递归写法:


1
2
3
4
5
6
7
8
9
func fib(N int) int {

if N <= 1 {
return N
}

return fib(N-1) + fib(N-2)

}

写法简洁,但效率却很低,会出现大量重复计算…(解决重复计算,优先考虑到的办法就是动态规划)

时间复杂度为: O(2的n次方)

即约为根号5分之一 * [1.118的n次方- (-0.618)的n次方]




非递归写法:


1
2
3
4
5
6
7
8
9
10
func fib(N int) int {

a,b := 0,1 //这其实就是f(0)和f(1)

for i := 0; i < N; i++ {
a, b = b, a+b //每次循环,依次变为1,1 / 1,2 / 2,3 / 3,5 / 5,8...
}

return a
}

时间复杂度为: O(n)


斐波那契数列的三种时间复杂度



动态规划解法: