并行处理算法的渐近最坏时间复杂度：理论定义与实践考量

并行算法的复杂度从来不是单一套用串行复杂度规则定义的，你提出的疑问本质是混淆了并行算法不同维度的复杂度度量，以及理想理论模型和现实硬件的差异。

国内外通用算法教材（含《算法导论》并行算法章节、经典并行算法专业教材）对并行程序的复杂度，不会用单一的时间复杂度指标概括，而是先约定计算模型，再通过两个核心维度做度量：

• 基准理论模型约定：理论分析最常用的是PRAM（并行随机存取机）模型，默认假设处理器数量无限、共享内存访问无延迟、进程调度无开销、同步无成本，所有可并行的任务都能立刻分配到空闲处理器执行。
• 核心度量1：工作复杂度（Work），记为W(n)。指算法执行过程中所有处理器完成的操作总数量，和并行度无关，相当于把整个算法完全串行执行一遍需要的时间。对你举的例子：O(p)个进程各自执行O(n)操作，总工作复杂度固定为W = O(pn)，这个值不会随可用处理器数量变化。
• 核心度量2：跨度（Span/Depth，也叫关键路径长度），记为D(n)。指算法中由数据依赖、执行顺序决定的必须串行执行的最长操作链长度，也就是PRAM理想模型（无限处理器）下能达到的最短运行时间。还是你举的例子：如果这O(p)个进程从启动到结束完全独立，没有任何同步、依赖、数据交互，那最长执行链就是单个进程的执行时间，跨度D = O(n)；如果进程之间需要全局同步、或者存在先后依赖，跨度会更高。
• 基于两个核心度量，有普适的工作-跨度定律：不管你实际可用的物理处理器数量是多少（记为k），算法的实际运行时间T_k一定满足：
  T_k ≥ max(W/k, D)
  这个定律可以直接回答你的核心疑问：不存在“无论p和n的相对规模如何，整体运行时间都是O(n)”的结论。举个最直白的例子：如果p=1000，每个进程跑O(n)的独立任务，你手里只有k=1个处理器，那只能把1000个进程的任务串行跑完，实际运行时间是O(1000n)=O(pn)，和p直接相关；只有当可用处理器数k≥p的时候，才能同时跑满所有进程，这时候运行时间才会落到跨度的下界O(n)上。

理论PRAM模型的假设在现实中完全不成立，实际分析并行程序运行时间的时候，除了工作和跨度，还要考虑几个绕不开的成本：

• 物理核心数上限：消费级CPU核心数普遍在8-32之间，单路服务器CPU核心数多在百级以内，哪怕是并行能力最强的GPU，单卡的计算单元数量也是固定有限值。如果启动的进程/线程数p远大于物理核心数，操作系统会通过时间片轮转调度切换任务，额外的上下文切换开销会随p增长，不仅不会提速，反而可能让运行时间随p升高。
• 通信与同步开销：现实中多进程访问共享内存需要处理缓存一致性、锁竞争，分布式场景下跨节点通信走网络的延迟更是比本地计算高几个数量级。如果p个进程在执行中需要同步状态、交换数据，这部分开销通常是O(log p)甚至O(p)量级，会直接叠加到总运行时间里，p越大这部分开销越高。
• 调度与负载不均衡成本：把p个任务分配到k个核心上本身就有调度开销，如果任务之间的执行时长差异大，会出现部分核心提前跑完闲置、部分核心还在过载运行的情况，实际运行时间会远高于理论值W/k。
• 串行段瓶颈：也就是阿姆达尔定律描述的规律：如果算法里有固定比例的逻辑是必须串行执行、无法并行的，那不管你加多少处理器、开多少进程，整体加速比都会被这个串行段锁死上限，不可能达到理想的并行效率。

最后给出明确结论：你提到的场景下，只有在理想无限处理器、进程完全独立无任何额外开销的前提下，运行时间才是O(n)；只要处理器数量有限、或者存在同步通信成本，运行时间一定会受p的影响，不可能脱离p的规模谈并行时间复杂度。

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