如何计算时间复杂度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表示法的核心规则展开推导:
- 大O表示法的本质是描述输入规模趋向无穷时,函数增长的上界,计算时会忽略和输入规模无关的固定常数系数、以及远低于主导阶的低阶常数项。
- 展开两个线性操作的实际运行时间:假设第一个O(N)操作的耗时为
a*N + c1,第二个O(M)操作的耗时为b*M + c2,其中a、b为和输入规模无关的固定系数,c1、c2为操作的固定启动开销。总耗时为a*N + b*M + (c1 + c2)。 - 等价性验证:取固定常数
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
相关产品推荐
相关产品推荐

