不相关的非主导术语是否应该被删除？

Question

当我们有了时O(N + logN)，我们就不再logN是一个非主导术语。

当我们有时，O(N + M)我们必须保留这两个术语，因为这些术语不相关。

如果我们有类似的事情会发生什么O(N + logM)？一方面，术语仍然不相关。另一方面，即使M非常大并且N非常小，N迟早会超越logM，所以也许N应该被视为主导术语。在这种情况下应该logM放弃吗？

Answer 1

因为我们使用大 O 表示法，所以我们对上限感兴趣。对于第一种情况，O(N + logN)我们可以省略，logN因为它的增长速度比 慢N。请参见图表。

最后两种情况应该保留这两项，因为我们不能确定在常见情况下什么增长缓慢或增长更快。