求解1||sum(Uj)问题的非抢占式调度算法时间复杂度咨询

嘿，针对你问的单机器下最小化逾期作业数（也就是1||sum(Uj)问题）的非抢占式调度算法复杂度，我来给你拆解清楚：

这个问题的经典最优解就是Moore-Hodgson算法，它是个贪心算法，先理清楚它的步骤，再分析复杂度：

算法步骤 #

• 第一步：把所有作业按照截止期限d_j从小到大排序。这一步是整个算法的基础，确保我们优先处理时间要求更紧的作业。
• 第二步：遍历排序后的作业，维护一个当前的调度序列：
  1. 把当前作业加入序列，计算新的完成时间。
  2. 如果加入后这个作业逾期了（完成时间 > 该作业的截止期限），就从当前序列里找出处理时间p_j最长的作业，把它从序列中移除——因为移除耗时最长的作业，能最大程度缩短总完成时间，给后续作业留出更多空间，从而最小化最终的逾期作业数。

时间复杂度分析 #

这里的复杂度取决于你怎么实现第二步里的“找最长处理时间作业”：

• 如果用普通数组维护当前序列，每次找最大值需要遍历整个序列，那这一步的总时间是O(n²)，加上第一步排序的O(n log n)，整体复杂度就是O(n²)。
• 但如果用最大堆（优先队列）来维护当前序列的处理时间，每次插入和移除最大值的操作都是O(log k)（k是当前堆里的作业数，最多为n），那么第二步的总时间就是O(n log n)，加上排序的O(n log n)，整体的最优时间复杂度就是O(n log n)。

要强调的是，这个算法是被证明能得到该问题最优解的，贪心策略的正确性在于：优先处理截止早的作业，且在出现逾期时移除“最占用时间”的作业，能最大化按时完成的作业数量，正好对应最小化逾期作业数的目标。

内容的提问来源于stack exchange，提问作者es483