algorithm - O(max(m,n)) の時間の複雑さを理解する

Question

時間の複雑さが O(max(m,n)) である単純なプログラムまたはアルゴリズムを与えられた体はありますか。漸近記法を理解しようとしています。私はいくつかのチュートリアルに従い、O(n) と O(n^2) などの説明を理解しました。

しかし今、私は O(max(m,n)) の時間の複雑さとそれがどのように計算されるかを理解したいと思っています。これを実証するためのサンプル プログラムまたはアルゴリズムを教えてください。

Answer 1

big-O 記法を初めて研究するときに証明する一般的な定理は、次のとおりです。

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

言い換えれば、実行時間が O(max{m, n}) であるアルゴリズムは、実行時間も O(m + n) であるため、この時間の複雑さを持つアルゴリズムはすべて適合します。

この特定の例として、2 つの文字列を受け取り、最初の文字列が 2 番目の文字列の部分文字列であるかどうかを返すKnuth-Morris-Pratt 文字列照合アルゴリズムを考えてみましょう。実行時間は Θ(m + n) = Θ(max{m, n}) です。つまり、実行時間は 2 つの文字列のうち長い方の長さに比例します。

これが直観的にランタイム max{m, n} を持つものを与えない場合は申し訳ありませんが、数学的にはうまくいきます。

お役に立てれば！

Answer 2

私が考えることができるのは、Pythonのizip_longest関数です:

各イテラブルから要素を集約するイテレータを作成します。iterable の長さが不均一な場合、欠損値は fillvalue で埋められます。反復は、最も長い iterable が使い果たされるまで続きます。

例えば：

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

あなたの質問に対する最良の答えは、Robert Harvey のコメントだと思います。私の意見では、この種の境界が使用されるアルゴリズムの良い例はDFS.

これで疑問が解消されることを願っています：

DFS は、グラフのすべての頂点とすべてのエッジを調べます。Letnはグラフの頂点の数をm表し、グラフのエッジの数を表します。

DFS上記の観察に基づいて、 asの時間計算量の上限を導き出すことができますO(max(n, m))。

DFSの時間計算量をだけで制限できないグラフがあることに注意してくださいO(n)。完全なグラフは一例です。

DFSまた、 の時間計算量をだけで制限できないグラフもありますO(m)。null グラフはその例です。