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 string-matching algorithm , 它接受两个字符串并返回第一个字符串是否是第二个字符串的子字符串。运行时间为 Θ(m + n) = Θ(max{m, n})，这意味着运行时间与两个字符串中较长字符串的长度成线性关系。

如果这没有给出直观具有运行时 max{m, n} 的东西，我深表歉意，但从数学上讲这确实可行。

希望这对您有所帮助!