假设N和M是算法的两个参数.以下简化是否正确?
O(N+NM) = O[N(1+M)] = O(NM)换句话说,是否可以在这种情况下删除常量?
解决方案TL; DR 是
说明
根据Big-Oh表示法的定义,对于所有足够大的变量值,如果O(.)内部的项证明是小于常数乘以另一个项的常数,则可以删除较小的项.
>您可以在此处找到更精确的定义.但是一些示例后果是:
-
O(1000 * N + N ^ 2)= O(N ^ 2),因为N ^ 2会在N> 1000时使1000 * N变小
-
O(N + M)无法简化
因为N + NM <O,所以n = O(N + NM)= O(NM). N> 1和M> 1 分别为2(NM)
Suppose that N and M are two parameters of an algorithm. Is the following simplification correct?
O(N+NM) = O[N(1+M)] = O(NM)In other words, is it allowed to remove the constant in such a context?
解决方案TL;DR Yes
Explanation
By the definition of the Big-Oh notation, if a term inside the O(.) is provably smaller than a constant times another term for all sufficiently large values of the variable, then you can drop the smaller term.
You can find a more precise definition of Big-Oh here, but some example consequences are that:
O(1000*N+N^2) = O(N^2) since N^2 will dwarf 1000*N as soon as N>1000
O(N+M) cannot be simplified
O(N+NM) = O(NM) since N+NM < 2(NM) as soon as N>1 and M>1
更多推荐
O(N + NM)可以简化为O(NM)吗?
发布评论