O(N+NM) 可以简化为 O(NM) 吗？
Can O(N+NM) be simplified to O(NM)?
假设N和M是一个算法的两个参数。以下简化是否正确？
O(N+NM) = O[N(1+M)] = O(NM)
换句话说，是否允许在这种情况下删除常量？
显然，如果 M=0，则无法删除 N 项。所以让我们假设 M>0。取一个常量 k > 0 使得 1<=kM（如果 M 是整数，k=1，否则取一个常量 c 使得 0 < c <= M 取 k=1/c).我们有
N+NM = N(1+M)
<= N(kM+M) ; 1<=kM
= (k+1)NM
∊ O(NM)
另一方面，
NM <= N+NM ∊ O(N+NM)
因此相等。
TL;DR 是
说明
根据 Big-Oh 表示法的定义，如果 O(.) 中的一个项被证明小于一个常数乘以另一个项的所有足够大的变量值，那么您可以删除较小的任期。
您可以找到 Big-Oh here 的更精确定义，但一些示例结果是：
O(1000*N+N^2) = O(N^2) 因为一旦 N>1000
[=33，N^2 就会使 1000*N 相形见绌=]
O(N+M)无法化简
O(N+NM) = O(NM) 因为 N+NM < 2(NM) 一旦 N>1 且 M>1
假设N和M是一个算法的两个参数。以下简化是否正确？
O(N+NM) = O[N(1+M)] = O(NM)
换句话说，是否允许在这种情况下删除常量？
显然，如果 M=0，则无法删除 N 项。所以让我们假设 M>0。取一个常量 k > 0 使得 1<=kM（如果 M 是整数，k=1，否则取一个常量 c 使得 0 < c <= M 取 k=1/c).我们有
N+NM = N(1+M)
<= N(kM+M) ; 1<=kM
= (k+1)NM
∊ O(NM)
另一方面，
NM <= N+NM ∊ O(N+NM)
因此相等。
TL;DR 是
说明
根据 Big-Oh 表示法的定义，如果 O(.) 中的一个项被证明小于一个常数乘以另一个项的所有足够大的变量值，那么您可以删除较小的任期。
您可以找到 Big-Oh here 的更精确定义，但一些示例结果是：
O(1000*N+N^2) = O(N^2) 因为一旦 N>1000
[=33，N^2 就会使 1000*N 相形见绌=]O(N+M)无法化简
O(N+NM) = O(NM) 因为 N+NM < 2(NM) 一旦 N>1 且 M>1