(27)Go记忆化搜索和动态规划

了解记忆化搜索和动态规划前，先看一个普通的递归函数实现斐波那契数列的例子

上图，斐波那契数列的定义

// 普通递归函数的实现方法
func fib(n int) int {
    if n == 0 {
        return 0
    }
    if n == 1 {
        return 1
    }
    return fib(n-1) + fib(n-2)
}
该实现方法不好的地方是存在大量重复运算，用求第5个斐波那契数的图示说明，如下图：

如上图示，浪费太多资源做重复的事情，很自然就会想到能不能加个缓存，将结果存储在缓存中，
下次求该值，先去缓存中寻找，找到直接返回，找不到再去计算，这种思想就是记忆化搜索
实现如下：
// 记忆化搜索优化
// 算法复杂度O(n) 自上而下解决问题
func fib2(n int) int {
    // n从零到n,共n+1个位置
    memo := make([]int, n+1)

    // 递归函数
    var f func(n int) int
    f = func(n int) int {
        sum++
        if n == 0 {
            return 0
        }

        // 缓存中能找到值,直接返回该值
        if memo[n] != 0 {
            return memo[n]
        }

        // 计算该值并将该值存储在memo[n]中,下次不用重复计算
        if n == 1 {
            memo[n] = 1
        } else {
            memo[n] = f(n-1) + f(n-2)
        }
        return memo[n]
    }

    // f(n)为第n个斐波那契数
    return f(n)
}

动态规划和记忆化搜索相反，是自下而上解决问题，定义如下：
动态规划: 将原问题拆解成若干个子问题,同时保存子问题的答案,使得每个子问题只求解一次, 
最终获得原问题的答案
具体实现：
// 动态规划：时间复杂度O(n)，自下而上解决问题
func fib3(n int) int {
    if n == 0 {
        return 0
    }

    memo := make([]int, n+1) //从0到n,共n+1个元素
    memo[0] = 0
    memo[1] = 1

    for i := 2; i <= n; i++ {
        sum++
        memo[i] = memo[i-1] + memo[i-2]
    }
    return memo[n]
}

测试这3种方法性能 //
func main() {
    t := time.Now()
    fmt.Println(fib(40)) 
    fmt.Println("普通递归函数花费时间", t.Sub(time.Now()))
    fmt.Println("========")

    t2 := time.Now()
    fmt.Println(fib2(40)) 
    fmt.Println("记忆化搜索花费时间", t2.Sub(time.Now()))
    fmt.Println("========")

    t3 := time.Now()
    fmt.Println(fib3(40))
    fmt.Println("动态规划花费时间", t3.Sub(time.Now()))
}

测试结果
102334155
普通递归函数花费时间 -1.667709146s
========
102334155
记忆化搜索花费时间 -40.555µs
========
102334155
动态规划花费时间 -21.188µs

总结：普通递归函数性能很差，动态规划性能最好，记忆化搜索次之，
因为记忆化搜索在递归调用中花费更多时间

有bug欢迎指出

最后编辑于：2020.09.11 15:57:16