简单的递归方法
使用递归计算斐波拉契数列，写起来简单。
由于没保存中间结果，所以每一步都要重复计算，超过40就会变慢。
func Fib1(n uint) uint { // version1, 计算斐波拉契数列 // 使用递归。超过40后，由于重复计算就会很慢 if n == 1 || n == 2 { return 1 } return (Fib1(n-2) + Fib1(n-1)) }
使用数组保存中间结果
使用数组保存中间结果，避免了重复计算。
func Fib2(n uint) uint { // version2, 计算斐波拉契数列 // 时间复杂度O(N)，空间复杂度O(1) if n == 1 || n == 2 { return 1 } // 将中间结果保存在数组中，避免重复计算 var fibarr = [3]uint{0,1,0} var j uint = 2 for ; j <= n; j++ { fibarr[2] = fibarr[0] + fibarr[1] fibarr[0] = fibarr[1] fibarr[1] = fibarr[2] } return fibarr[2] }
完整示例代码
go实现
package main import ( "fmt" "time" ) func Fib1(n uint) uint { // version1, 计算斐波拉契数列 // 使用递归。超过40后，由于重复计算就会很慢 if n == 1 || n == 2 { return 1 } return (Fib1(n-2) + Fib1(n-1)) } func Fib2(n uint) uint { // version2, 计算斐波拉契数列 // 时间复杂度O(N)，空间复杂度O(1) if n == 1 || n == 2 { return 1 } // 将中间结果保存在数组中，避免重复计算 var fibarr = [3]uint{0,1,0} var j uint = 2 for ; j <= n; j++ { fibarr[2] = fibarr[0] + fibarr[1] fibarr[0] = fibarr[1] fibarr[1] = fibarr[2] } return fibarr[2] } func main() { startTime := time.Now() var i uint = 1 for ; i < 10; i++ { fmt.Printf("%d, %d\n",i,Fib2(i)) } endTime := time.Since(startTime) fmt.Println("计算用时",endTime) }
python实现
from time import time def fib1(number: int) -> int: if number == 1 or number ==2: return 1 return fib1(number-2) + fib1(number-1) def fib2(number: int) -> int: if number == 1 or number ==2: return 1 fibarr = [0,1,0] j = 2 while j <= number: fibarr[2] = fibarr[0] + fibarr[1] fibarr[0] = fibarr[1] fibarr[1] = fibarr[2] j += 1 return fibarr[2] if __name__ == '__main__': start_time = time() print(fib1(40)) end_time = time() print(f"fib1 耗时 {(end_time - start_time):.4f} seconds") start_time2 = time() print(fib2(40)) end_time2 = time() print(f"fib2 耗时 {(end_time2 - start_time2):.4f} seconds")
