排序算法之：最小平均等待时间调度（Shortest Job First, SJF）的贪心策略证明与算法实现
字数 2840 2025-12-21 08:26:10

排序算法之：最小平均等待时间调度（Shortest Job First, SJF）的贪心策略证明与算法实现

题目描述
假设有一个单线程CPU，需要处理一系列作业（jobs）。每个作业都有一个处理时间（processing time），表示完成这个作业所需的CPU时间。当一个作业到达CPU时，如果CPU空闲，它会立即开始执行；否则，它需要在队列中等待，直到CPU完成当前作业。
我们需要设计一个调度策略，安排作业的执行顺序，以使得所有作业的平均等待时间最小。
形式化描述如下：
给定一个数组 jobs，其中 jobs[i] 表示第 i 个作业的处理时间。假设所有作业的到达时间均为0，我们需要找到一个排列 π，表示作业的执行顺序，使得：
平均等待时间 = (所有作业等待时间的总和) / 作业个数 最小。
其中，一个作业的等待时间定义为：从时刻0到该作业开始执行的时间间隔。
求最小平均等待时间，并给出调度顺序的构造算法。

解题过程循序渐进讲解

第一步：理解等待时间的计算方式
假设我们有三个作业，处理时间分别为 [3, 1, 2]。
如果我们按照原顺序 [3, 1, 2] 执行：

  • 作业1（时间3）：从时刻0开始，结束于时刻3，等待时间 = 0。
  • 作业2（时间1）：从时刻3开始，结束于时刻4，等待时间 = 3。
  • 作业3（时间2）：从时刻4开始，结束于时刻6，等待时间 = 4。
    总等待时间 = 0 + 3 + 4 = 7，平均等待时间 = 7/3 ≈ 2.333。

如果我们按照 [1, 2, 3] 的顺序执行：

  • 作业2（时间1）：等待时间 = 0。
  • 作业3（时间2）：等待时间 = 1。
  • 作业1（时间3）：等待时间 = 1+2 = 3。
    总等待时间 = 0 + 1 + 3 = 4，平均等待时间 = 4/3 ≈ 1.333。
    显然，第二种顺序的平均等待时间更小。

观察发现：短作业先执行似乎能减少等待时间。

第二步：形式化问题与猜想
设作业的执行顺序为 J1, J2, …, Jn，对应的处理时间为 p1, p2, …, pn。
那么：

  • J1 开始于时刻0，等待时间 W1 = 0。
  • J2 开始于时刻 p1，等待时间 W2 = p1。
  • J3 开始于时刻 p1 + p2，等待时间 W3 = p1 + p2。
  • …
  • Jk 开始于时刻 p1 + p2 + … + p(k-1)，等待时间 Wk = p1 + p2 + … + p(k-1)。

总等待时间 T = W1 + W2 + … + Wn
= 0 + p1 + (p1 + p2) + (p1 + p2 + p3) + … + (p1 + p2 + … + p_{n-1})。

我们可以将 T 重写为：
T = (n-1)p1 + (n-2)p2 + (n-3)p3 + … + 1p_{n-1} + 0*pn。

因此，T 是处理时间 p_i 的加权和，权重从后往前依次是 0, 1, 2, …, n-1，但顺序是由作业顺序决定的。
换句话说，如果我们把作业按处理时间从小到大排序，让时间最短的作业放在最前面，那么它会被更多后续作业“等待”，但它本身的权重小，从而减少总等待时间。
这引出了贪心策略猜想：将作业按处理时间非递减顺序排序（最短作业优先，SJF）可最小化总等待时间。

第三步：贪心策略的证明（交换论证法）
假设最优调度顺序不是按处理时间非递减排序的，则存在相邻两个作业 A 和 B，A 在 B 之前执行，但 A 的处理时间 > B 的处理时间（即长作业在短作业之前）。
设 A 的处理时间为 a，B 的处理时间为 b，且 a > b。
考虑交换 A 和 B 的位置，其他作业顺序不变。我们需要分析交换对总等待时间的影响。

交换前，在 A 之前的所有作业的总时间记为 S，则：

  • A 的开始时间 = S，等待时间 = S。
  • B 的开始时间 = S + a，等待时间 = S + a。
  • 在 B 之后的某个作业 C 的开始时间会增加 a + b（来自 A 和 B 的处理时间之和）。

交换后（B 在 A 之前）：

  • B 的开始时间 = S，等待时间 = S。
  • A 的开始时间 = S + b，等待时间 = S + b。
  • 作业 C 的开始时间仍然是 S + a + b（因为 a+b = b+a，和不变）。

现在比较交换前后，总等待时间的变化：

  • 对于 A 和 B 自身：
    交换前：A 等待 S，B 等待 S + a，合计 2S + a。
    交换后：B 等待 S，A 等待 S + b，合计 2S + b。
    因为 a > b，交换后合计减少 (a - b) > 0。
  • 对于其他作业（A 之前和 B 之后的作业），开始时间不变，因此等待时间不变。

因此，交换后总等待时间严格减少，这与原调度是最优的矛盾。
所以，最优调度中不可能存在相邻逆序（即长作业在短作业之前），故最优顺序就是按处理时间非递减排序的顺序。

第四步：算法实现
根据以上分析，算法非常简单：

  1. 对 jobs 数组按处理时间升序排序。
  2. 计算总等待时间：
    • 设 currentTime = 0，totalWait = 0。
    • 遍历排序后的数组，对于每个作业时间 p：
      • 该作业等待时间 = currentTime。
      • totalWait += currentTime。
      • currentTime += p。
  3. 平均等待时间 = totalWait / n。

例如，jobs = [3, 1, 2]：

  • 排序后 [1, 2, 3]。
  • 作业1（时间1）：等待 0，totalWait = 0，currentTime = 1。
  • 作业2（时间2）：等待 1，totalWait = 1，currentTime = 3。
  • 作业3（时间3）：等待 3，totalWait = 4，currentTime = 6。
  • 平均等待时间 = 4/3 ≈ 1.333。

第五步：扩展到作业有不同到达时间的情况
如果作业有不同到达时间，问题变得更复杂（成为“最短剩余时间优先”调度，SRTF），通常需要用优先队列动态选择当前可执行的、处理时间最短的作业。但本题目假设所有作业到达时间均为0，因此只需简单排序即可。

第六步：时间复杂度与优化
排序需要 O(n log n) 时间，计算等待时间需要 O(n) 时间，总时间复杂度 O(n log n)。空间复杂度 O(1)（如果原地排序）。这是该问题的最优复杂度，因为排序是必要步骤。

总结
本题展示了贪心算法的一个经典应用：通过交换论证证明最短作业优先（SJF）调度在平均等待时间最小化问题上的最优性。关键在于将总等待时间表达为处理时间的加权和，然后证明任何逆序都会增加总等待时间。算法实现简单高效，是调度理论和操作系统中一个基础且重要的结论。

排序算法之：最小平均等待时间调度（Shortest Job First, SJF）的贪心策略证明与算法实现 题目描述 假设有一个单线程CPU，需要处理一系列作业（jobs）。每个作业都有一个处理时间（processing time），表示完成这个作业所需的CPU时间。当一个作业到达CPU时，如果CPU空闲，它会立即开始执行；否则，它需要在队列中等待，直到CPU完成当前作业。 我们需要设计一个调度策略，安排作业的执行顺序，以使得所有作业的 平均等待时间 最小。 形式化描述如下： 给定一个数组 jobs ，其中 jobs[i] 表示第 i 个作业的处理时间。假设所有作业的到达时间均为0，我们需要找到一个排列 π ，表示作业的执行顺序，使得： 平均等待时间 = (所有作业等待时间的总和) / 作业个数 最小。 其中，一个作业的等待时间定义为：从时刻0到该作业开始执行的时间间隔。 求最小平均等待时间，并给出调度顺序的构造算法。 解题过程循序渐进讲解 第一步：理解等待时间的计算方式 假设我们有三个作业，处理时间分别为 [3, 1, 2] 。 如果我们按照原顺序 [3, 1, 2] 执行： 作业1（时间3）：从时刻0开始，结束于时刻3，等待时间 = 0。 作业2（时间1）：从时刻3开始，结束于时刻4，等待时间 = 3。 作业3（时间2）：从时刻4开始，结束于时刻6，等待时间 = 4。 总等待时间 = 0 + 3 + 4 = 7，平均等待时间 = 7/3 ≈ 2.333。 如果我们按照 [1, 2, 3] 的顺序执行： 作业2（时间1）：等待时间 = 0。 作业3（时间2）：等待时间 = 1。 作业1（时间3）：等待时间 = 1+2 = 3。 总等待时间 = 0 + 1 + 3 = 4，平均等待时间 = 4/3 ≈ 1.333。 显然，第二种顺序的平均等待时间更小。 观察发现： 短作业先执行 似乎能减少等待时间。 第二步：形式化问题与猜想 设作业的执行顺序为 J1, J2, …, Jn ，对应的处理时间为 p1, p2, …, pn 。 那么： J1 开始于时刻0，等待时间 W1 = 0。 J2 开始于时刻 p1，等待时间 W2 = p1。 J3 开始于时刻 p1 + p2，等待时间 W3 = p1 + p2。 … Jk 开始于时刻 p1 + p2 + … + p(k-1)，等待时间 Wk = p1 + p2 + … + p(k-1)。 总等待时间 T = W1 + W2 + … + Wn = 0 + p1 + (p1 + p2) + (p1 + p2 + p3) + … + (p1 + p2 + … + p_ {n-1})。 我们可以将 T 重写为： T = (n-1) p1 + (n-2) p2 + (n-3) p3 + … + 1 p_ {n-1} + 0* pn。 因此，T 是处理时间 p_ i 的加权和，权重从后往前依次是 0, 1, 2, …, n-1，但顺序是由作业顺序决定的。 换句话说，如果我们把作业按处理时间从小到大排序，让时间最短的作业放在最前面，那么它会被更多后续作业“等待”，但它本身的权重小，从而减少总等待时间。 这引出了贪心策略猜想： 将作业按处理时间非递减顺序排序（最短作业优先，SJF）可最小化总等待时间 。 第三步：贪心策略的证明（交换论证法） 假设最优调度顺序不是按处理时间非递减排序的，则存在相邻两个作业 A 和 B，A 在 B 之前执行，但 A 的处理时间 > B 的处理时间（即长作业在短作业之前）。 设 A 的处理时间为 a，B 的处理时间为 b，且 a > b。 考虑交换 A 和 B 的位置，其他作业顺序不变。我们需要分析交换对总等待时间的影响。 交换前，在 A 之前的所有作业的总时间记为 S，则： A 的开始时间 = S，等待时间 = S。 B 的开始时间 = S + a，等待时间 = S + a。 在 B 之后的某个作业 C 的开始时间会增加 a + b（来自 A 和 B 的处理时间之和）。 交换后（B 在 A 之前）： B 的开始时间 = S，等待时间 = S。 A 的开始时间 = S + b，等待时间 = S + b。 作业 C 的开始时间仍然是 S + a + b（因为 a+b = b+a，和不变）。 现在比较交换前后，总等待时间的变化： 对于 A 和 B 自身： 交换前：A 等待 S，B 等待 S + a，合计 2S + a。 交换后：B 等待 S，A 等待 S + b，合计 2S + b。 因为 a > b，交换后合计减少 (a - b) > 0。 对于其他作业（A 之前和 B 之后的作业），开始时间不变，因此等待时间不变。 因此，交换后总等待时间严格减少，这与原调度是最优的矛盾。 所以，最优调度中不可能存在相邻逆序（即长作业在短作业之前），故最优顺序就是按处理时间非递减排序的顺序。 第四步：算法实现 根据以上分析，算法非常简单： 对 jobs 数组按处理时间升序排序。 计算总等待时间： 设 currentTime = 0 ， totalWait = 0 。 遍历排序后的数组，对于每个作业时间 p ： 该作业等待时间 = currentTime 。 totalWait += currentTime 。 currentTime += p 。 平均等待时间 = totalWait / n 。 例如， jobs = [3, 1, 2] ： 排序后 [1, 2, 3] 。 作业1（时间1）：等待 0，totalWait = 0，currentTime = 1。 作业2（时间2）：等待 1，totalWait = 1，currentTime = 3。 作业3（时间3）：等待 3，totalWait = 4，currentTime = 6。 平均等待时间 = 4/3 ≈ 1.333。 第五步：扩展到作业有不同到达时间的情况 如果作业有不同到达时间，问题变得更复杂（成为“最短剩余时间优先”调度，SRTF），通常需要用优先队列动态选择当前可执行的、处理时间最短的作业。但本题目假设所有作业到达时间均为0，因此只需简单排序即可。 第六步：时间复杂度与优化 排序需要 O(n log n) 时间，计算等待时间需要 O(n) 时间，总时间复杂度 O(n log n)。空间复杂度 O(1)（如果原地排序）。这是该问题的最优复杂度，因为排序是必要步骤。 总结 本题展示了贪心算法的一个经典应用：通过交换论证证明最短作业优先（SJF）调度在平均等待时间最小化问题上的最优性。关键在于将总等待时间表达为处理时间的加权和，然后证明任何逆序都会增加总等待时间。算法实现简单高效，是调度理论和操作系统中一个基础且重要的结论。