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)。