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

Question

是否可以给定一个时间复杂度为 O(max(m,n)) 的简单程序或算法。我试图理解渐近符号。我遵循了一些教程并理解了他们解释的内容，即 O(n) 和 O(n^2)。

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

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} 的东西，我深表歉意，但从数学上讲，这确实有效。

希望这可以帮助！

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不会增加所需的时间。

Answer 3

最简单的例子是

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

从理论上：O(max(m,n))只是O(m+n)

“现实生活”的例子O(max(m,n))可能是算法，它分别为两个未排序的数组m和n- 找到两者的最大元素

Answer 4

我认为您问题的最佳答案是罗伯特哈维的评论。在我看来，使用这种边界的算法的一个很好的例子是DFS.

我希望，这将消除您的疑虑：

DFS 检查图的每个顶点和每个边。Letn表示图中的顶点数，并m表示图中的边数。

DFS根据上述观察，您可以推导出as的时间复杂度的上限O(max(n, m))。

请注意，有些图的时间复杂度不能DFS由限制O(n)。一个完整的图表就是一个例子。

此外，有些图的时间复杂度不能DFS仅由限制O(m)。空图就是一个例子。