理解O(max(m,n))时间复杂度

Question

有没有人能给出一个时间复杂度为O(max(m,n))的简单程序或算法？我正在尝试理解渐近符号。我已经学习了一些教程，理解了它们所解释的O(n)和O(n^2)。

但现在我想了解O(max(m,n))的时间复杂度以及如何计算它。请给出一个示例程序或算法来演示这一点。

- user2684719

---

max是什么？它只是m和n中的较高者吗？如果是这样，那么如果m大于n，它就是简单的O(m)，如果n大于m，它就是O(n)。 - Robert Harvey

Answer 1

在学习大O符号时，常见的一个定理是：

Θ(max{m, n}) = Θ(m + n)

换句话说，任何运行时间为O(max{m, n})的算法也具有O(m + n)的运行时间，因此任何具有这种时间复杂度的算法都可以胜任。

作为一个具体的例子，考虑Knuth-Morris-Pratt字符串匹配算法，它接受两个字符串并返回第一个字符串是否为第二个字符串的子串。运行时间为Θ(m + n) = Θ(max{m, n})，这意味着运行时间与两个字符串中较长的那个的长度成线性关系。

如果这不直观地表明了运行时间为max{m, n}，我很抱歉，但从数学上讲，这确实是正确的。

希望这能帮到你！

- templatetypedef

---

@Gray 没错! 已经修复了。很好的发现！ - templatetypedef

Answer 2

我能想到的一个是Python中的izip_longest函数：

创建一个迭代器，它从每个可迭代对象中聚合元素。 如果可迭代对象长度不同，则使用fillvalue填充缺失的值。迭代继续直到最长的可迭代对象用完。

例如：

In [1]: from itertools import zip_longest

In [2]: list(zip_longest([1, 2, 3, 4, 5, 6, 7], ['a', 'b', 'c']))
Out[2]: [(1, 'a'), (2, 'b'), (3, 'c'), (4, None), (5, None), (6, None), (7, None)]

In [3]: list(zip_longest([1, 2], ['a', 'b', 'c']))
Out[3]: [(1, 'a'), (2, 'b'), (None, 'c')]

In [4]: list(zip_longest([1, 2, 3], ['a', 'b', 'c']))
Out[4]: [(1, 'a'), (2, 'b'), (3, 'c')]

这应该很清楚，为什么这是一个 O(max(m, n)) 操作而不是 O(m+n) 操作，据我所知；因为当 m > n 时，增加 n 不会增加所需的时间。

- utdemir

---

实际上，对于多个变量的合理定义，Θ(m+n)与Θ(max(m,n))是相同的。如果n和m中的一个支配另一个，则Θ(某些总和)的通常推理适用。如果n和m大致相似，则Θ(n+m)和Θ(max(n,m))都简化为Θ(2n)（或Θ(2m)，它们是相同的），这又可以简化为Θ(n)。尽管如此，我已经在其他地方论证过带有+号的版本也具有教育意义。 - user395760

Answer 3

最简单的例子是

for i=0 to max(m,n)
     print 'a'

从理论上讲：O(max(m,n)) 就是 O(m+n) 一个“现实生活”中的例子是，对于两个大小分别为m和n的未排序数组，找到它们中最大的元素的算法。

- lejlot

---

如果 O(max(m,n)) 只是 O(m+n)，那为什么不直接说 O(m+n) 呢？ - Robert Harvey

他们可能强调了最大部分。描述给定函数的顺序有很多种方式。例如，添加非零常数不会改变顺序。或者对数的底数等等。 - Joel

@Robert，正如Joel所说 - 最有可能的原因是强调如果我们进行严格的成本分析，那么实际上是最大操作，但在O符号中并不重要，因为max(m,n)=THETA(m+n)（从复杂性意义上讲，这些函数是等价的），这是1/2(m+n) <= max(m,n) <= m+n <= 2*max(m.n)的明显结果。 - lejlot

Answer 4

我认为对你的问题最好的回答是Robert Harvey的评论。在我看来，一个使用这种限制的算法的好例子是DFS。

我希望这能解决你的疑惑：

DFS检查图的每个顶点和每条边。设n表示图中顶点的数量，m表示边的数量。

基于上述观察，您可以得出DFS时间复杂度的上界为O(max(n, m))。

请注意，有些图形的时间复杂度不能仅通过O(n)来限制DFS的时间复杂度。完全图是一个例子complete graph。

同样，有些图形的时间复杂度不能仅通过O(m)来限制DFS的时间复杂度。空图是一个例子null graph。

- pkacprzak