go语言基础之斐波那契数列

2025/4/20 11:13:36 来源：https://blog.csdn.net/xsw164711368/article/details/141284117 浏览: 次关键词：go语言基础之斐波那契数列

概述

本文描述了用go语言分别用递归与循环的方式，计算出斐波那契数列，并对比了执行程序所花销的时间

递归函数的时间复杂度是Tn=O(f(n)),它表示随问题规模n的增大，算法的执行时间增长率和f (n)增长率成正比，这称作算法的渐进时间复杂度。
为了解决效率问题，可以将递归方式转换为循环方式，达到以空间换时间的效果。循环方式计算斐波拉契数列对应值时间复杂度仅O(n)。

代码实现

递归方式


package mainimport ("fmt""time"
)/*
用递归方式计算斐波拉契数列
*/func fibonacci(n int) (res int) {if n<=1 {// n==0或n==1时，返回值为1return 1} else {// n>=2时，结果需要递归计算前2位的值return fibonacci(n-1) + fibonacci(n-2)}
}func main()  {// 记录开始时间start := time.Now().Unix()	num := 52// 给定一个值,计算结果fmt.Println(fibonacci(num))	// 打印总耗时fmt.Println("total(s):",time.Now().Unix() - start)
}

循环方式计算

利用数组保存计算出的数值，斐波那契数数列后面的数可以通过数组之前保存的数来计算，避免了重复迭代计算，所以时间复杂度是O(1)

在这里插入代码片
package mainimport ("fmt""time"
)/*
以切片作为存储，用循环方式计算斐波拉契数列
相比递归方式，以空间换时间
*/func fibonacci(n int) []int {// 定义切片，用于保存结果var numList []intres := 0for i:=0;i<=n;i++ {if i==0 {numList = append(numList,1)} else if i==1 {numList = append(numList,1)} else {// 如果是n>=2，每个当前的值，等于切片的前2位之和res = numList[i-1] + numList[i-2]numList = append(numList,res)}}return numList
}func main()  {// 定义切片，用于保存结果var numList []int// 记录开始时间start := time.Now().Unix()num := 52// 给定一个值,计算结果numList = fibonacci(num)fmt.Println(numList[num])// 打印总耗时fmt.Println("total(s):",time.Now().Unix() - start)
}