performance - O(M+N) とはどういう意味ですか?

Question

これは基本的な質問です...しかし、O(M+N) は O(max(M,N)) と同じであると考えています。これは、無限大になると、より大きな項が支配するはずだからですか? また、それは O(min(M,N)) とは異なりますね。私はこの表記法を見続けています。グラフアルゴリズムについて議論するとき。たとえば、O(|V| + |E|) (例: http://algs4.cs.princeton.edu/41undirected/ ) が日常的に表示されます。

Answer 1

はい、O(M+N) は O(max(M, N)) と同じ意味です。これは O(min(M, N)) とは異なります。@Dr_Asik が言うように、O(M+N) は技術的には線形の O(N) ですが、M と N に意味がある場合、「何が線形なのか?」と言えると便利です。アルゴリズムが行数と列数に関して線形であると想像してください。N = 行 + 列を定義して O(N) とするか、O(M+N) (M は行、N は列) と定義できます。

Answer 2

線形時間は O(N) と表記されます。(M+N) は一次関数であるため、O(N) とも表記する必要があります。同様に、O(1) を O(2)、O(10) などと比較しても意味がありません。それらはすべて一定時間であり、すべて O(1) と表記する必要があります。