程序员经典面试题，设计定时任务调度器

评估一个算法，我们既要考虑它的查询算法复杂度，也要考虑他的插入算法复杂度。在定时任务场景中，很显然，查询场景是非常多的。几乎我们每个单位时间都要轮询一遍，那么我们有没有优化算法的可能呢?

我们每次查询，都只要查询时间最接近当前时间的，时间比当前时间更早的，肯定被我们丢弃了。所以这个题目，等价于我们查询队列里面时间最小的。我们不禁想到一个熟悉的数据结构，优先队列!活着我们可以使用一个小根堆进行实现。

每次我们插入一个新的定时任务，我们将一个任务插入优先队列，每次插入的时候，队列内部需要进行调整，算法时间复杂度为O(logN)。值得注意的是，在讨论算法时间复杂度的时候，logN是Base2的，也就是说，如果N等于8的时候，logN就是3。

同理，虽然我们可以在O(1)的时间里面找到时间最小的任务，但是如果我们取出这个元素，优先队列需要做内部的调整，这个算法时间复杂度也是O(logN)的。

时间轮法

上述优先队列的算法，综合算法时间复杂度是O(logN)的，已经很高效了，但是在我们大并发的分布式系统下，这个速度，还是太慢了。我们有没有更高效的算法呢?

那便是时间轮算法，时间轮是一个环形队列，按照时间的单位区分，我们假设1秒，每个单位里面，是一个链表，用来存储定时任务。

（编辑：南通站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!