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)

换句话说，是否可以在这种情况下删除常量?

解决方案

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)吗?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！