理解 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} 的东西，我很抱歉，但从数学上讲，这确实有效。

希望这可以帮助！