Fibonacci数列
原创
Fibonacci 数列是一种在数学中非常著名的数列，其定义如下：
- Fibonacci 数列的第一个数为 0（有时也以 1 为第一个数），第二个数为 1。
- 其后的每一个数都是前两个数之和。即：
因此，Fibonacci 数列的前几个数是：
Go 语言实现基础版 Fibonacci 数列
在 Go 语言中，可以用递归、循环或记忆化递归来实现 Fibonacci 数列。我们先来看一个最基础的递归实现。
package main
import "fmt"
// 递归计算Fibonacci数列
func fibonacci(n int) int {
if n <= 1 {
return n
}
return fibonacci(n-1) + fibonacci(n-2)
}
func main() {
n := 10 // 求第10个Fibonacci数
fmt.Println(fibonacci(n))
}这个递归实现非常直观，直接按照 Fibonacci 数列的定义进行计算。然而，基础的递归实现有一些严重的性能问题。
性能问题分析
上述递归方法在计算 Fibonacci 数时会出现大量的重复计算。例如，在计算 fibonacci(5) 时需要计算 fibonacci(4) 和 fibonacci(3)，而计算 fibonacci(4) 时又要计算 fibonacci(3) 和 fibonacci(2)，这样 fibonacci(3) 就被计算了多次。随着 n 的增大，这种重复计算的次数呈指数级增长，导致算法的时间复杂度为 O(2^n)。
Go 语言优化版 Fibonacci 数列
为了优化 Fibonacci 数列的计算，我们可以采用以下几种方法：
1. 记忆化递归
通过使用一个数组或映射来存储已经计算过的 Fibonacci 值，避免重复计算。这种技术叫做“记忆化”。
package main
import "fmt"
// 记忆化递归计算Fibonacci数列
func fibonacci(n int, memo map[int]int) int {
if n <= 1 {
return n
}
if val, ok := memo[n]; ok {
return val
}
memo[n] = fibonacci(n-1, memo) + fibonacci(n-2, memo)
return memo[n]
}
func main() {
n := 10 // 求第10个Fibonacci数
memo := make(map[int]int)
fmt.Println(fibonacci(n, memo))
}记忆化递归显著减少了重复计算，将时间复杂度降至 O(n)。
2. 动态规划
动态规划方法通过从下往上计算 Fibonacci 数列，逐步累积结果，而不需要递归。这是最常用的优化手段。
package main
import "fmt"
// 动态规划计算Fibonacci数列
func fibonacci(n int) int {
if n <= 1 {
return n
}
fib := make([]int, n+1)
fib[0] = 0
fib[1] = 1
for i := 2; i <= n; i++ {
fib[i] = fib[i-1] + fib[i-2]
}
return fib[n]
}
func main() {
n := 10 // 求第10个Fibonacci数
fmt.Println(fibonacci(n))
}这种方法也将时间复杂度降低为 O(n)，并且由于只需记录前两个 Fibonacci 数，因此空间复杂度可以进一步优化到 O(1)。
3. 滚动数组优化
我们可以进一步优化动态规划算法，使其只使用常数级别的空间。因为在计算第 n 个 Fibonacci 数时，只需要用到前两个数，所以只需两个变量存储前两个数的值。
package main
import "fmt"
// 滚动数组优化计算Fibonacci数列
func fibonacci(n int) int {
if n <= 1 {
return n
}
a, b := 0, 1
for i := 2; i <= n; i++ {
a, b = b, a+b
}
return b
}
func main() {
n := 10 // 求第10个Fibonacci数
fmt.Println(fibonacci(n))
}在这个版本中，空间复杂度已经优化到 O(1)，依然保持时间复杂度为 O(n)。
最后
- 基础的递归方法直观但效率低下，适用于小规模计算。
- 记忆化递归通过避免重复计算，显著提升了递归方法的效率。
- 动态规划通过从下往上的方式计算 Fibonacci 数列，进一步提升效率。
- 滚动数组优化在动态规划的基础上进一步降低了空间复杂度，使算法更加高效。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
腾讯云开发者
