针对程序员的经典面试问题，设计预定的任务计划程序，使用哪种算法与数据结构

在我还是学生的时候，我参加了一个重逢时代的采访. 面试问题有了新的记忆任务调度算法，因此您可以完成计划的任务. 你会怎么做？为了简化问题，我们只需要考虑内存方案，而不是数据持久性.

数组方法

最简单的方法是，我们可以将所有任务存储在一个数组中，然后每单位时间遍历整个数组，以查找是否有一个任务满足当前时间，如果有，则从数组中取出并执行. 每单位时间查询算法的复杂度为O（N）. 那么，如何执行一项新任务？我们只需将一个元素添加到数组中，算法时间复杂度为O（1）

优先队列方法

要评估算法，我们必须同时考虑其查询算法复杂度和插入算法复杂度. 在计划任务方案中，很明显，有许多查询方案. 几乎我们必须每单位时间轮询一次，因此我们可以优化算法吗？每次查询时，只要查询时间最接近当前时间，该时间就会早于当前时间，并且必须将其丢弃. 因此，这个问题等于我们查询队列中的最小时间. 我们不禁想到一个熟悉的数据结构，优先级队列！活着的我们可以使用一个小的根堆来实现. 每次插入新的定时任务时，都会将任务插入优先级队列. 每次插入时，都需要调整队列，算法时间复杂度为O（logN）. 值得注意的是，在讨论算法时间复杂度时，logN为Base2，即N为8，logN为3. 类似地，尽管我们可以找到O（1）时间最小的任务，在此元素之外，需要在内部调整优先级队列，算法时间复杂度也为O（logN）.

时间轮方法

上面优先级队列的算法，综合算法时间复杂度为O（logN），已经非常有效，但是在我们的大型并发分布式系统中，这个速度仍然太慢. 我们有更有效的算法吗？那就是时间轮算法. 时间轮是循环队列，根据时间单位进行划分. 我们假设1秒. 每个单元中都有一个链接列表，用于存储定时任务.

您可能会问，循环队列中的元素毕竟是优先级. 如果超过长度任务调度算法，该怎么办？我们可以想到我们家的水表，它也有很多轮子，并且每个轮子的单位都不同！时间轮也是如此. 我们可以使用多级时间轮进行优化. 就像我们的时钟或水表一样，这一层走来走去，下一层走来走去.

那么，如何计算该算法的时间复杂度？插入时，我们从最低层搜索以找到哪一层，然后直接插入相应的比例. 如果我们的时轮有5层，那么我们最多可以搜索5次. 查询时，我们每秒推动一次时间轮的滚动，并且每次我们直接进入团队的第一个元素时，这等效于算法O（1）的时间复杂度. 转弯时，再次向下推下一层的下一个单元. 这样，我们的一个元素将从第5层逐渐插入到第1层，集成的一个元素最多将插入5次. 在评估算法时间复杂度时，我们通常会忽略常数和最终算法时间，复杂度为O（1）.

摘要

一个非常简单的面试问题，有几种不同的解决方案. 这就是算法和数据结构的魅力. 欢迎大家跟随我，共同学习，共同进步. 所有人的支持是我继续聊天的动力.

本文来自本站，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-257476-1.html