问O(mn)比O((m+n)^2)好吗？

EN

因此，许多评论者和答复者只想考虑m = n时的情况，或者至少当他们与常量因素相关时。这不是这样的。

当我们保持m或n常数时，您的算法显然更快；例如，如果我们将自己局限于情况m = 1，那么算法的复杂性是O(n)，而替代方法是O(n^2)，因此在这种受限情况下，您的算法显然更好。

我们可以说的是，(m+n)^2 = m^2 + n^2 + 2mn显然是Ω(mn)，Ω的意思是这是一个下界，而您的算法总是(渐近的)至少是一样好的；也就是说，没有限制的情况下，其他算法的渐近性优于您的算法。但我们确实知道，在某些情况下，你的情况更好。所以，总的来说，你的更好。

是的，你的实现更好。回想一下(m+n)^2 = m^2 + n^2 + 2mn，so (m+n)^2 > mn

O(mn)并非在所有情况下都优于O((m+n)²)。

看看这个案子：

O((m+n)²) = O(mn) if m=O(n)

对于m=O(n)，be可以引入一个新变量(c:= max(n,m))

O((m+n)²) = O(m² + 2mn + n²) 
           = O(c² + 2cc + c²=
           = O( 3* c²)
           = O(c²)

O(mn)      = O(cc) = O(c²)

因此，在n和m仅差一个常数的情况下，这两个复杂性是相同的。

正如注释中所提到的，如果不是，则是 m=O(n)

O(mn)比O(n²) > O(nm)或O(m²) > O(mn)更好。

My Fazit:取决于您对“更好”的定义，您可以说：

O(mn)从来没有比O((m+n)²)更糟糕

或

O(mn)比O((m+n)²)好