O（m + n）和O（mn）之间的区别？

我试图通过不同的方法来发现算法的复杂性。从数学上讲，我遇到了一个O（m +

n）和另一个O（mn）方法。但是，我无法理解或说出这种形象。好像我看着他们并没有感觉到“啊！那是怎么回事”的感觉！有人可以使用自己的示例或任何其他工具对此进行解释吗？

我对发现直觉的建议是思想实验，如下所示：

首先，认识到m和n是 输入的 两个 不同度量

。它们可能是两个输入流的长度，矩阵边的长度，或同一数据结构的两个不同属性的计数，例如同一图形的边和节点计数，或任何类似的度量。

直觉是big-O用一个简单的函数-称R（m，n）-乘以某个值来表示算法的真实

运行时间（或其他方面，例如比较计数或所需空间）的界限。任意常数。我们忽略了常数因素，并通过调用运行时间O（R（m，n））来考虑所有以同一R为界的算法。

因此，大O（m + n）表示，对于合适的大m和n，实际运行时间受某个函数R（m，n）= C（m +

n）限制。对于图示例，这表示算法的实际运行时间将受顶点和边的数量之和的倍数限制。

您可以将边界函数看作是3d中具有轴m，n和R（m，n）的图形。或者您可以想到图表：

R(m,n) = m + n
--------------
m=  1  2  3  4
n=1 1  2  3  4
  2 3  4  5  6
  3 4  5  6  7
  4 5  6  7  8

对于R（m，n）= mn，您有

R(m,n) = mn
--------------
m=  1  2  3  4
n=1 1  2  3  4
  2 2  4  6  8
  3 3  6  9 12
  4 4  8 12 16

作为3d图形，第一个函数是一个平面，第二个函数是在几乎所有点上都快得多的增长函数。这意味着，如果m和n足够大，则O（mn）边界最终将比O（m +

n）大（对应于可能更慢的程序），因为常量变得无关紧要了。

以快速增长的成本为例，假设O（m + n）算法在其运行时范围内具有3的额外常数（与上述两种算法相比，在小输入量下它的运行速度可能非常慢）：

R(m,n) = 3(m + n)
--------------
m=   1  2  3  4
n=1  3  9 12 15
  2  9 12 15 18
  3 12 15 18 21
  4 15 18 21 24

因此，与上表中的O（mn）相比，O（m + n）的约束似乎受约束的程度要小。但是看一下m = n = 100的情况。此处，在O（m +

n）算法上的界限是3（m + n）=600。但是常数较小的O（mn）算法的界限mn =10000。显然，如果m和n大，则您要第一个。

@Anonymous在本文的初始版本中提出了一个很好的观点，它混淆了big-O和big-Theta。Big-O仅处理被测数量的界限或上限

。例如，这意味着每个 O（n）算法也是O（n log n）和O（n ^ 2）。如果实际运行时间受较慢增长的函数限制，则它也受所有较快增长的函数限制。

然而，人们常常说“此算法为O（n）”，而这意味着边界是 紧密的

。也就是说，对于某些常数C，Cn是运行时间的上限，而对于其他常数D（合适的是较大的n），Dn也是下限。这样的严格界限正确地表示为Theta（n），而不是O（n）。Theta（R（m，n））算法的运行时间（大致而言）与R（m，n）成比例。

最后我要补充一点，在许多情况下，您不能忽略常量。文献中存在许多算法，它们比通常使用的算法渐近“快”，但是常数太大，以至于实际问题的规模总是太慢。计算几何有很多例子。基数2排序是另一种。它是Theta（n），但实际上，一个好的快速排序（Theta（n

log n）平均大小）将在大小至少为10 ^ 8的整数数组上胜过它。