algorithm - 如果已知 m 在所有情况下都小于 n，O(n+m) 是否等于 O(n)？

Question

我可能记错了。我认为这是因为在大 O 表示法中没有忽略常量吗？我对所有这些算法分析的东西都很陌生。任何帮助将不胜感激？

我正在遍历一个数组，跟踪另一个数组中的计数，然后遍历第二个数组以跟踪运行计数。

Answer 1

是的。如果m总是最多n，那么 O(n+m) 是 O(n+n) 是 O(2n) 是 O(n)。

正如@phs 在评论中指出的那样，即使m是最多X*n（对于固定的X）也是如此：然后 O(n+m) 是 O(n+X*n) 是 O(Y*n) 是 O( n)。