公告:“业余草”微信公众号提供免费CSDN下载服务(只下Java资源),关注业余草微信公众号,添加作者微信:xttblog2,发送下载链接帮助你免费下载!
本博客日IP超过2000,PV 3000 左右,急需赞助商。
极客时间所有课程通过我的二维码购买后返现24元微信红包,请加博主新的微信号:xttblog2,之前的微信号好友位已满,备注:返现
受密码保护的文章请关注“业余草”公众号,回复关键字“0”获得密码
所有面试题(java、前端、数据库、springboot等)一网打尽,请关注文末小程序
腾讯云】1核2G5M轻量应用服务器50元首年,高性价比,助您轻松上云
本博客日IP超过2000,PV 3000 左右,急需赞助商。
极客时间所有课程通过我的二维码购买后返现24元微信红包,请加博主新的微信号:xttblog2,之前的微信号好友位已满,备注:返现
受密码保护的文章请关注“业余草”公众号,回复关键字“0”获得密码
所有面试题(java、前端、数据库、springboot等)一网打尽,请关注文末小程序
![视频教程免费领](https://cdn.jsdelivr.net/gh/xmt1139057136/xttblog/2022/03/1648866767704.jpg)
腾讯云】1核2G5M轻量应用服务器50元首年,高性价比,助您轻松上云
Memoization 被很多人翻译成记忆,是根据字面意思来翻译的。今天我就来说一说记忆化算法。
它其实是一种很巧妙的思想或设计,被称为算法,我想主要是因为它经常会和一些算法进行搭配使用吧。
Memoization 应该有很大的使用场景的,举个例子。我们现在要算一个斐波那契数列,对于一个已经算过的数,就没必要再进行计算一遍了。我们可以把这个数之前算过的结果从缓存中取出来。
比如类似下面的斐波那契数列。
0,1,1,2,3,5,8,13,21,34,55,89,144 ..
它们具有以下递归关系:
F(n)= F(n-1)+ F(n-2)
在 Java 中我们可以靠递归函数来实现。
// Fibonacci without Memoization
public int fibonacci(int n){
if( n == 0 ) return 0;
if( n == 1 ) return 1;
System.out.println("Calculating fibonacci number for: "+n);
return (fibonacci(n-1) + fibonacci(n-2));
}
现在,我们可以输入任意数进行计算。但是,当我重复计算一个数时,它并没有记忆,并没有记住上次对该数计算对结果。还是会一层一层的递归计算。
![](https://java2blog.com/wp-content/uploads/2018/08/FibonacciMemoizationExample.jpg)
解决这类问题的办法就是,采用缓存,把之前计算过的数字直接缓存起来。下次再调用就先判断缓存中是否有没有,没有的化再计算,否则直接从缓存中读取。
public class FibonacciMemoizationAlgorithm {
private Map<Integer, Integer> memoizeTable = new HashMap<>(); // O(1)
// Fibonacci with Memoization
public int fibonacciMemoize(int n){
if( n == 0 ) return 0;
if( n == 1 ) return 1;
if( this.memoizeTable.containsKey(n) ) {
System.out.println("Getting value from computed result for "+n);
return this.memoizeTable.get(n);
}
int result = fibonacciMemoize(n-1)+ fibonacciMemoize(n-2);
System.out.println("Putting result in cache for "+n);
this.memoizeTable.put(n, result);
return result;
}
// Fibonacci without Memoization
public int fibonacci(int n){
if( n == 0 ) return 0;
if( n == 1 ) return 1;
System.out.println("Calculating fibonacci number for: "+n);
return (fibonacci(n-1) + fibonacci(n-2));
}
public static void main(String[] args) {
FibonacciMemoizationAlgorithm fibonacciAlgorithm = new FibonacciMemoizationAlgorithm();
System.out.println("Fibonacci value for n=5: "+fibonacciAlgorithm.fibonacciMemoize(5));
}
}
这就是记忆化的原理,不同的场景采用的缓存技术不同,但原理基本都类似。
最后,欢迎关注我的个人微信公众号:业余草(yyucao)!可加作者微信号:xttblog2。备注:“1”,添加博主微信拉你进微信群。备注错误不会同意好友申请。再次感谢您的关注!后续有精彩内容会第一时间发给您!原创文章投稿请发送至532009913@qq.com邮箱。商务合作也可添加作者微信进行联系!
本文原文出处:业余草: » Java中的记忆(Memoization)算法