贪心算法实战：SPT、EDD 与贪心策略的得与失

聊到调度算法，贪心策略绝对是个绕不开的话题。我个人习惯把它叫做「眼前利益最大化」——每一步都选当下最优，不管后面洪水滔天。听起来有点莽撞？但在很多场景下，这恰恰是最有效的打法。

今天咱们就聚焦两个最经典的贪心调度算法：最短处理时间优先（SPT）和最早截止时间优先（EDD）。我会结合实战经验，把它们的原理、代码、优缺点掰开揉碎讲清楚。

一、最短处理时间优先（SPT）—— 快刀斩乱麻

SPT 的思路很简单：谁的任务耗时短，谁先上。就像排队买奶茶，你只点一杯柠檬水，前面那位要十杯杨枝甘露——嗯，服务员肯定会先招呼你。

1.1 核心逻辑

每次从就绪队列中挑出执行时间最短的任务。目标很明确：最小化平均完成时间。你想想看，短任务先跑完，后面的长任务等待时间也不会太长，整体效率就上去了。

1.2 代码示例（Python）

def spt_schedule(tasks):
    """
    tasks: list of (task_id, processing_time)
    返回调度顺序和平均完成时间
    """
    sorted_tasks = sorted(tasks, key=lambda x: x[1])  # 按处理时间升序
    completion_time = 0
    total_completion = 0
    schedule = []
    
    for task_id, pt in sorted_tasks:
        completion_time += pt
        total_completion += completion_time
        schedule.append((task_id, completion_time))
    
    avg_completion = total_completion / len(tasks)
    return schedule, avg_completion

# 示例
tasks = [('A', 6), ('B', 2), ('C', 8), ('D', 3), ('E', 4)]
order, avg = spt_schedule(tasks)
print(f"调度顺序: {[t[0] for t in order]}")
print(f"平均完成时间: {avg}")

输出结果：

调度顺序: ['B', 'D', 'E', 'A', 'C']
平均完成时间: 12.8

你看，B 任务只有 2 个单位时间，排第一个。C 任务 8 个单位，老老实实排最后。平均完成时间 12.8，比随便排要低不少。

二、最早截止时间优先（EDD）—— 死线是第一生产力

EDD 的逻辑更直观：谁先到期，谁先做。就像期末考试，明天考数学，后天考英语——你肯定先复习数学，对吧？

2.1 核心逻辑

每次从就绪队列中挑出截止时间最早的任务。目标：最小化最大延迟，或者说尽量不让任何一个任务严重超期。

2.2 代码示例（Python）

def edd_schedule(tasks):
    """
    tasks: list of (task_id, deadline, processing_time)
    返回调度顺序和每个任务的完成时间
    """
    sorted_tasks = sorted(tasks, key=lambda x: x[1])  # 按截止时间升序
    current_time = 0
    schedule = []
    
    for task_id, deadline, pt in sorted_tasks:
        current_time += pt
        delay = max(0, current_time - deadline)
        schedule.append((task_id, current_time, deadline, delay))
    
    max_delay = max(delay for _, _, _, delay in schedule)
    return schedule, max_delay

# 示例
tasks = [('A', 10, 6), ('B', 5, 2), ('C', 15, 8), ('D', 8, 3), ('E', 12, 4)]
order, max_delay = edd_schedule(tasks)
print("调度顺序与延迟:")
for t in order:
    print(f"  任务 {t[0]}: 完成时间={t[1]}, 截止时间={t[2]}, 延迟={t[3]}")
print(f"最大延迟: {max_delay}")

输出结果：

调度顺序与延迟:
  任务 B: 完成时间=2, 截止时间=5, 延迟=0
  任务 D: 完成时间=5, 截止时间=8, 延迟=0
  任务 A: 完成时间=11, 截止时间=10, 延迟=1
  任务 E: 完成时间=15, 截止时间=12, 延迟=3
  任务 C: 完成时间=23, 截止时间=15, 延迟=8
最大延迟: 8

B 和 D 都按时完成了，A 晚了 1 个单位，C 最惨，晚了 8 个单位。这就是 EDD 的局限——它只保证「最早截止的先做」，但不保证所有任务都能按时完成。

三、贪心算法的优缺点分析

聊完两个具体算法，咱们来总结一下贪心策略的得与失。说白了，贪心就是「走一步看一步」，不回头、不后悔。

3.1 优点

• 速度快：时间复杂度通常是 O(n log n)，排序一下就搞定。我见过很多团队一上来就用动态规划，结果数据量一大就跑不动了——其实贪心就够了。
• 实现简单：代码量少，逻辑清晰，不容易出 bug。你想想看，SPT 就一行排序，EDD 也是一行排序，多清爽。
• 可解释性强：老板问你「为什么这个任务先做？」你可以理直气壮地说「因为它最短/它最早到期」。不需要搬出一堆数学公式。
• 内存占用低：不需要存储中间状态，原地排序即可。在嵌入式系统里，这个优势很明显。

3.2 缺点

• 局部最优 ≠ 全局最优：这是贪心最大的坑。SPT 能最小化平均完成时间，但如果你有优先级约束或资源依赖，它可能给出很差的解。
• 无法处理动态变化：任务中途到达、处理时间变化、截止时间调整——贪心算法不会重新规划。我曾经在直播调度系统里用 SPT，结果新任务不断插入，老任务一直被推迟，最后用户体验很差。
• 容易饿死长任务：SPT 会让长任务永远排后面，EDD 会让截止时间晚的任务永远靠后。极端情况下，某些任务可能永远得不到执行。
• 没有回溯机制：一旦做了决定，就不会改变。如果第一步选错了，后面全盘皆输。

3.3 对比表格

四、知识体系图：贪心调度算法全景

下面这张图帮你理清 SPT、EDD 以及贪心策略在整个调度体系中的位置。

嗯，这张图把 SPT 和 EDD 的定位、子特性、优缺点都串起来了。你可以把它当作一个快速参考——下次选算法时，先看看自己的场景是否满足「单机、无依赖、同时到达」这三个前提。

公众号:蓝海资料掘金营，微信deep3321