O(N+NM)可以简化为O(NM)吗？

Question

假设N和M是算法的两个参数。以下简化是否正确？

O(N+NM) = O[N(1+M)] = O(NM)

换句话说，是否允许在这种情况下删除常量？

Answer 1

TL；博士是

解释

根据大噢表示法的定义，如果O(.)中有一个术语可以证明，对于变量的所有足够大的值，它都小于常量乘以另一个项，则可以删除较小的项。

你可以找到一个更精确的大欧这里的定义，但是一些例子的结果是：

• O(1000*N+N^2) = O( N^2 )，因为N^2一N>1000就会使1000*N变矮
• O(N+M)不能简化
• O( N+NM ) = O(NM)自N+NM< 2(NM)起，由N>1和M>1开始

Answer 2

显然，如果是N，则不能去掉M=0术语。所以让我们假设M>0。取一个常量k > 0，使1<=kM (如果M是整数，则为k=1，则取一个常量c，使0 < c <= M an取k=1/c)。我们有

N+NM  = N(1+M)
     <= N(kM+M)            ; 1<=kM
      = (k+1)NM
      ∊ O(NM)

另一方面，

NM <= N+NM ∊ O(N+NM)

因此，平等。