最短作业优先算法通过最小堆数据结构实现。 那么SJF算法的时间复杂度是多少呢？
我在某处读到它是 n*2*log n，等于 n log n .请解释如何。 (对不起，如果问题太简单了。我是新手。
提前谢谢。
插入和提取分钟操作的运行时间为O(log n)。有n个任务，每个任务都必须插入到堆中，然后从堆中提取，从而导致运行时间为O(n log n)。
Insert的运行时间为O(log n)的原因是，在插入时，我们首先将新任务添加到堆最终位置。这不一定会维护堆属性，因为新任务的优先级可能比其父任务的优先级更好(具有较小的键(。这就是Insert操作涉及堆化过程的原因，该过程的目的是还原堆顺序。Heapify-Up过程的运行时间为O(log n)。
Extract-Min的运行时间为O(log n)的原因是，在Extract-Min操作中，我们首先删除堆的根(第一个任务(，然后将最后一个任务移动到第一个位置(即，将根替换为驻留在最后一个位置的任务(。由于这可能违反堆属性，因此Extract-Min涉及执行堆下行过程。Heapify-Down过程的运行时间为O(log n).
非抢占式 sjf 可以使用段树在 O(nlogn( 时间复杂度中完成。 获取结构中进程的输入，并根据 到达时间。现在，我们将使用段树来查找范围最小突发时间和相应的进程 ID，这将需要2*logn进行查询并更新两者。