了解O(max(m，n))的时间复杂度 [英] Understanding Time complexity of O(max(m,n))

问题描述

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

但是现在我想了解O(max(m，n))的时间复杂度及其计算方式. 请提供一个示例程序或算法来证明这一点.

Can some body given a simple program or algorithm whose Time complexity is O(max(m,n)). I am trying to understand asymptotic notations. I followed some tutorials and understood what they have explained that i.e O(n), and O(n^2).

But now I want to understand Time complexity for O(max(m,n)) and how it is calculated. Please give a sample program or algorithm to demonstrate this.

推荐答案

初次研究big-O表示法时要证明的一个常见定理是:

A common theorem to prove when studying big-O notation for the first time is that

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

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

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

In other words, any algorithm whose runtime is O(max{m, n}) also has runtime O(m + n), so any algorithm with this time complexity will fit the bill.

作为一个具体示例，请考虑 Knuth-Morris-Pratt字符串匹配算法，它接收两个字符串，并返回第一个字符串是否为第二个字符串的子字符串.运行时间为Θ(m + n)=Θ(max {m，n})，这意味着运行时间在两个字符串中较长者的长度上是线性的.

As a specific example of this, consider the Knuth-Morris-Pratt string-matching algorithm, which takes in two strings and returns whether the first string is a substring of the second. The runtime is Θ(m + n) = Θ(max{m, n}), meaning that the runtime is linear in the length of the longer of the two strings.

如果这不能给出直观地具有运行时间max {m，n}的东西，我对此表示歉意，但是从数学上讲，这确实可以解决问题.

I apologize if this doesn't give something that intuitively has runtime max{m, n}, but mathematically this does work out.

希望这会有所帮助！

这篇关于了解O(max(m，n))的时间复杂度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！