作业不抢占时最短作业​​优先算法的时间复杂度

Question

最短作业优先算法通过最小堆数据结构实现。 那么SJF算法的时间复杂度是多少？

我在什么地方读它，这是N * 2 *日志n的等于n日志ñ。请解释如何。 （很抱歉，如果这个问题太easy.I是新来的吧。）事先

感谢。

Answer 1

Insert和Extract-Min操作的运行时间都是O(log n)。有n任务，每个任务必须插入到堆中，然后从堆中提取，导致运行时间为O(n log n)。

Insert的运行时间为O(log n)的原因是插入时我们先将新任务添加到堆的最终位置。这并不一定保持heap property，因为新任务的优先级可能比其父级的优先级更高（具有更小的密钥）。这就是为什么Insert操作涉及Heapify-Up procedure，其目的是恢复堆顺序。 Heapify-Up程序的运行时间为O(log n)。

原因Extract-Min有O(log n)运行时间是在Extract-Min操作，我们先删除堆的根（第一个任务），然后最后一个任务移动到第一位置（即与更换根任务位于最后的位置）。由于这可能违反堆属性，因此Extract-Min涉及执行Heapify-Down procedure。 Heapify-Down程序的运行时间也为O(log n)。