O(N)与O(N+M)算法复杂度的区别及场景判定疑问

结论先行：处理两个长度分别为N和M的独立输入（比如两个字符串）时，时间复杂度应该标记为 O(N+M)，而不是直接简化为 O(N)——除非题目明确给出N和M存在固定的规模关系（比如M始终是N的常数倍）。

关键差异点 #

• 大O表示法的核心是描述算法在所有可能输入规模组合下的增长趋势，当N和M是两个完全独立的变量时，不能随意把其中一个合并到另一个里。比如极端情况：N=1，M=1000000，这时候算法的执行时间显然由M主导，但如果反过来N=1000000，M=1，就由N主导。如果只用O(N)，就无法覆盖这两种完全不同的输入场景。
• 你提到的“2N简化为N”只适用于同一变量的系数简化，比如O(2N)可以简化为O(N)，因为系数不影响增长量级。但O(N+M)里的N和M是两个独立的输入维度，不存在“系数”关系，除非有明确约束（比如M=O(N)），否则不能随意合并。

实际场景举例 #

比如一个字符串拼接算法，需要先遍历第一个字符串（长度N）复制所有字符，再遍历第二个字符串（长度M）复制所有字符，总操作数是N+M，这时候复杂度就是O(N+M)。如果题目说明“两个字符串长度始终相等”，那可以写成O(N)，但如果没有这个前提，必须保留O(N+M)，才能准确反映算法在任意输入下的性能表现。

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