同步阅读进度，多语言翻译，过滤屏幕蓝光，评论分享，更多完整功能，更好读书体验，试试 阅读 ‧ 电子书库
离线算法
与在线算法的通常假设不同，我们可能会一次提交众多问题实例批量解决，而不要求每个实例提交后就马上返回结果。
假设我们要实现一个字典，先在这个空字典中插入一个含有n个数字y1……yn的集合，然后进行n/2次的查询contains(xi):x1……xn/2。最优的数据结构是将每个yj插入到一个无序的数组Y中，复杂度为O(n)，然后通过在数组Y中顺序查找实现contains(xi)，这样的最差情况的复杂度为O(n)。所以这n+1次操作的总体最大复杂度为O(n)。
执行n/2次顺序查找的复杂度为O(n2)。由于无法预测下一个查询是什么，所以在线算法无法主动的为下一个特定的查询进行优化()。不过，如果我们在线下批量进行这n/2个查询，就可以分别将y1……yn以及x1……xn/2进行排序，存在有序数组Y和X中，这两个操作最坏情况的复杂度为O(n log n)，然后扫描这两个有序数组寻找重复元素，最坏情况复杂度为O(n)。批量进行n/2个查询的这种离线算法的最坏情况复杂度为O(n log n)，而如果执意在线算法，要求每个查询在下一个查询之前返回结果的话，最坏情况的复杂度则为O(n2)。
请支持我们，让我们可以支付服务器费用。
使用微信支付打赏
