在线算法和离线算法的区别
我们用LCA做例子，倍增算法先预处理每个点向上的路径，每次询问一对节点的时候，找到最近的2^k次公共祖先，然后向上跳2^(k-1)，一直到找到答案。来一个询问，就回答一次。Tarjan算法把这个询问作为一条边挂在树上，最后做一次遍历，用并查集快速查找当前这棵子树的根。得到所有询问后统一回答。
■网友
在线算法的输入是数据流，无须等待全部输入完成即可产生即时计算结果，简单的例子比如蓄水池抽样（reservoir sampling）算法。
■网友
区别就是能否实时的计算出结果作为反馈。3d动画电影和3d游戏的画面渲染就是非常典型的例子。3d动画电影都是离线渲染的，可以使用光线追踪之类非常复杂非常慢的算法渲染出非常逼真的画面，在性能强劲的工作站上几分钟一帧的速度都可以接受。3d游戏就必须实时渲染了，在主流配置的电脑上每一帧都必须在几十分之一秒内渲染出来立刻呈现到屏幕上，才使画面看起来连续。不过如同前面一位哥们说的静态光照贴图，游戏也会用到一些离线的预处理算法，把一些可以提前准备好的数据离线计算出来保存好，渲染时直接使用，典型的空间换时间策略。
■网友
当用户请求过来，要在几毫秒内计算完成的算法叫在线算法；在请求之前就计算好的，叫离线算法。
■网友
游戏图形引擎的静态光照贴图的烘焙就是离线算法，因为要产生高质量的lightmap可能需要几个小时，在线算法只计算动态物体的光照，毕竟游戏每秒要跑三十帧以上。
推荐阅读
- 互联网在线音乐行业有哪些可能的盈利模式
- Guleva|【GET2020】智学龙Maria Guleva：俄罗斯在线教育正在走向全球
- 现在在线学习视频有很多了，为啥大部分人还是喜欢下载下来观看
- 为啥这个算法误差的看起来这么小
- 阿里云|【GET2020】阿里云解航：在线教育帮助线下教育一起实现教育公平和个性化
- 资本|仅剩沉默的大多数在线教育融资2020：除了资本青睐的独角兽
- 视频|一天近700万人在线看其出生视频婴儿出生时羊水囊未破
- 使用算法帮助人们筛选reader的信息是否存在可能
- 请问如果想成为算法工程师的话，大学选专业是选软件工程好还是计算机科学与技术好。
- 哪个网站可以在线阅读台湾和香港的杂志或者报纸