多并行实例的Big O表示法疑问：O(max{...})还是O(n)？

并行执行场景 #

4个并行进程各自运行for n in messages: print(n)这类循环时，时间复杂度有两种合理表述：

• 精确表述为 O(max{f(n), g(n), h(n), i(n)})：并行任务是同时推进的，总耗时由其中运行时间最长的单个循环决定，和循环实例的数量无关。
• 简化表述为 O(n)：由于每个循环的规模都不超过n（n≤10），最大的单个循环耗时也不会超过O(n)，因此可以简化为这个结论。
  两种表述都正确，前者更精准，后者是简化后的通用结论。

单程序嵌套循环场景 #

单程序中执行for n in queues: for m in messages: print(m)这类嵌套循环时，时间复杂度是 O(k*m)（k为queues的规模，m为messages的规模）；当k和m都不超过给定的n时，也可表述为O(n²)。
原因是嵌套循环属于串行执行：外层每完成一次迭代，就会完整执行一遍内层循环，总操作次数是两层循环规模的乘积，耗时和总操作数直接正相关，因此时间复杂度为各层规模的乘积级。

核心差异总结 #

两种场景的时间复杂度差异本质源于执行模式的不同：

• 并行执行：多个任务同时推进，总耗时由单个任务的最长耗时决定，与任务数量无关；
• 串行嵌套：任务依次叠加执行，总耗时由各层循环的操作数乘积决定。

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