串行算法（serial algorithm）与并行算法（parallel algorithm）的区别是什么？

基础定义 #

你已经了解的串行/并行处理是硬件层面的执行模式，而串行/并行算法是脱离硬件的、提前设计的任务完成逻辑，二者的核心差异是步骤设计的思路不同。

串行算法 #

• 是描述单个执行流完成任务的步骤逻辑，所有步骤强依赖前序步骤的输出，不管用多少核心的硬件运行，都只能按顺序一步步执行，前一步没完成后一步根本无法启动。
• 举个简单例子：求普通递归版本的第N项斐波那契数，每一步计算都依赖前两项的结果，就算给100个核心也没法拆分计算，只能按递归顺序一步步算。

并行算法 #

• 是描述多个独立执行流协作完成同一任务的步骤逻辑，核心设计思路是把原任务拆成多个互不依赖（或依赖极低）的子任务，每个子任务可以单独跑在不同计算单元上，最后汇总结果得到最终输出。
• 同样拿数值计算举例：求1到10000的累加和，并行算法可以拆成10组分别算1-1000、1001-2000……的和，10个执行流同时计算，最后把10个分组的和相加得到最终结果，硬件核心足够的情况下速度可以接近串行版本的10倍。

二者核心实用差异 #

• 设计核心不同：串行算法不需要考虑依赖拆分，允许步骤之间任意复用前序输出；并行算法的设计重点就是拆分依赖，子任务之间的信息交互越多，并行效率就越低。
• 评价标准不同：串行算法只需要评估时间复杂度、空间复杂度两个核心指标；并行算法除了这两个，还要额外评估加速比（并行运行耗时/串行运行耗时，越高越好）、可扩展性（核心数增加时加速比能不能同步提升）、通信开销（多个执行流之间交换数据的耗时）。
• 适用场景不同：
  • 任务本身逻辑强依赖、无法拆分的场景，只能用串行算法，比如单链表遍历、状态依赖极强的状态机执行
  • 任务可以拆分为多个独立子任务的场景，适合用并行算法，比如大规模矩阵运算、图片批处理、分布式数据统计
• 需要处理的问题不同：串行算法只要保证逻辑正确、资源占用合理即可；并行算法还要额外处理死锁、资源竞争、数据一致性、负载均衡（部分子任务运行过慢拖慢整体速度）等问题。

代码示例对比 #

以计算数组所有元素的平方和为例：

串行算法实现（Python） #

def serial_square_sum(arr):
    total = 0
    for num in arr:
        total += num ** 2
    return total

整个流程只有一个循环，每一步都依赖上一步的total值，无法拆分执行。

并行算法实现（Python） #

from multiprocessing import Pool

def calc_part_sum(part):
    return sum(num **2 for num in part)

def parallel_square_sum(arr, process_cnt=4):
    # 拆分数组为4份，每个进程单独计算一份的平方和
    parts = [arr[i::process_cnt] for i in range(process_cnt)]
    with Pool(process_cnt) as pool:
        part_res = pool.map(calc_part_sum, parts)
    # 汇总所有子任务结果
    return sum(part_res)

各个子任务计算独立，没有数据依赖，仅最后汇总一次结果即可。

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