这个（非抢占式）调度算法的复杂度是多少？

Question

我对作业（非抢占式）调度算法的算法复杂度有疑问，该算法特别用于获得 1||sum(Uj) 问题（仅限一台机器）的最优解，其中 Uj是单一惩罚（即：如果作业在截止日期前终止，则等于 0，如果延迟终止，则等于 1）。

我需要最小化单一惩罚的总和（即：迟到作业的总和）。给定作业处理时间及其截止日期，并且没有释放时间（因此，所有作业在时间 t=0 时同步释放）。该算法的工作原理如下：

1- 根据最早截止日期对所有作业排序

2-找出第一个迟到的工作Jj。如果没有迟到的作业转到第 4 步。

3- 找出 Jj 和它的前辈之间处理时间最长的作业。删除该作业和 return 到步骤 2，考虑没有删除作业的新序列

4- 最佳序列由以下公式给出：当前序列[后跟] 在步骤 3 中以任何顺序删除的作业子集。

我被要求计算该算法的最坏情况 O(...) 复杂度，在一般且良好实施的情况下（因此，我必须尝试猜测复杂度 "implementation-free"时刻，给定所有算法步骤）。

我认为第 1 步需要 O(nlogn)，因为（使用 QuickSort 或 MergeSort）这只是一个排序问题。

但是，那么第 2-3-4 步呢？例如，如果我们尝试在 C/C++ 中实现它，那么声明最终复杂度可能为 O(n^2) 是否正确？或者是 O(n*logn) 由于 EDD "optimizing" 随后的搜索？确定其复杂性的可能证据是什么？

非常感谢。

Answer 1

在我看来，整个算法可以在 O(n log n) 时间内完成。基本思想是分摊移除前辈的成本。每次我们移除一个前任，我们将支付 O(log n)，并且最多移除 n 次。

这是具体细节。在第 1 步之后，您只需对作业进行一次传递，因为从序列中删除作业只会使作业更快完成。每次考虑序列中的作业时，您都会重复删除其最大的前任作业，直到它按时完成。请注意，"remove the largest predecessor" 操作的总数最多为 n，因为每个作业最多将被删除一次。 [注意：我认为这里需要注意一些，因为 "predecessor" 应该是一个包容性的概念。也就是说，当考虑一个特定的工作 j 时，如果 j 比以前的任何工作都大，那么你应该删除 j 并继续下一个工作。]

如何有效地实施 "remove the largest predecessor" 操作？您可以通过维护（当您从左到右浏览作业时）按作业大小 对前任作业的排序来做到这一点 。这种排序可以用例如二叉搜索树来实现，它允许在 O(log n) 中进行插入和删除。每次开始考虑一份工作时，您都会将其插入树中，并支付 O(log n)。删除最大的前任只是从树中删除最大的作业。

之前我们注意到最多会有 n 次删除，对应于树中最多 n 次删除。因此，我们为删除支付了 O(n log n) 的总成本。我们还为插入支付了 O(n log n) 的总成本（每个作业恰好是一个插入）。对所有数据进行排序的预处理步骤为O(n log n)，因此所有步骤的总成本为O(n log n).

这是一些伪代码：

J = input sorted by earliest due date
T = empty tree
for each j in J, from left to right:
  insert j into T
  while j does not finish on time:
    j' = delete largest from T
    if j' == j:
      break to next job in J

我遗漏的唯一细节是如何检查作业是否按时完成。但这非常简单，因为您可以简单地通过在树中插入和删除作业时从计数器中添加和减去来跟踪 "current finishing time"。

这个（非抢占式）调度算法的复杂度是多少？

What's the complexity of this (non-preemptive) scheduling algorithm?

algorithm

complexity-theory

scheduling

time-complexity