You need to enable JavaScript to run this app. 如何计算时间复杂度O(N)与O(M)的相加结果,O(N)+O(M)是否等价于O(N+M)?
优惠活动
大模型
产品
解决方案
定价
更多

如何计算时间复杂度O(N)与O(M)的相加结果,O(N)+O(M)是否等价于O(N+M)?

双独立规模线性操作的整体时间复杂度计算

顺序执行场景下的整体复杂度写法

当两个线性操作按先后顺序执行、无嵌套依赖关系,且两者的输入规模N、M为相互独立的变量(无固定函数映射关系,无法预先判断数值大小)时,整体时间复杂度的标准表示为 O(N + M)。
这种写法覆盖了所有输入组合的情况:

  • 若N远大于M:总耗时的主导项为N,O(N+M) 会退化为 O(N),和单线性复杂度的上界规则一致
  • 若M远大于N:总耗时的主导项为M,O(N+M) 会退化为 O(M)
  • 若N和M数值接近:总耗时的增长和单一线性规模的2倍增长等价,符合大O忽略常数系数的规则

O(N) + O(M) 与 O(N + M) 的等价性结论

在独立输入规模、顺序执行的前提下,两种表述完全等价。
其背后的原理可以从大O表示法的核心规则展开推导:

  1. 大O表示法的本质是描述输入规模趋向无穷时,函数增长的上界,计算时会忽略和输入规模无关的固定常数系数、以及远低于主导阶的低阶常数项。
  2. 展开两个线性操作的实际运行时间:假设第一个O(N)操作的耗时为 a*N + c1,第二个O(M)操作的耗时为 b*M + c2,其中a、b为和输入规模无关的固定系数,c1、c2为操作的固定启动开销。总耗时为 a*N + b*M + (c1 + c2)。
  3. 等价性验证:取固定常数 k = max(a, b),无论N、M的相对大小如何,都满足不等式:
    a*N + b*M ≤ k*N + k*M = k*(N + M)
    
    加上固定开销项属于可忽略的低阶项,因此总耗时的增长阶和 N + M 完全一致。两种表述只是形式上的拆分与合并,不存在本质差异。

常见误区提醒:上述加和等价规则仅适用于操作按顺序执行的场景。如果两个操作为嵌套调用/嵌套循环的关系,整体复杂度为乘法关系 O(N * M),既不满足两个复杂度的加和形式,也不能用 O(N + M) 表示。

内容的提问来源于stack exchange,提问作者AdmosJagashvili

相关产品推荐
方舟 Agent Plan

超全模态模型 × Harness 升级,最新支持 Deepseek-V4.1-Flash、GLM-5.3 系列、Doubao-Seedream-5.0-pro、Kimi-K3 (部分), 限时 9.9 元起

最近更新时间:2026.10.26 04:06:04