algorithm - 時間計算量が O(M+N) であるとはどういう意味ですか?

Question

言ってるのと同じか

O(max(M,N))? 

私は時間の複雑さを学んでいますが、このタイプの複雑さはグラフで何度も出てきます。それらが何を意味するのか完全には理解していません

O(M+N),

ここで、M=エッジの数 N=頂点の数。

Answer 1

O(M+N)と同じですかO(max(M,N))？

はい、同じです。一般性を失うことなく、それを言うことができますM >= N. したがって、O(max(M,N))と同じO(M)です。同時に、 は と同じでM < M+N < M+Mあり、O(M+N)はO(2*M)と同じO(M)です。

Answer 2

N頂点があると仮定すると、エッジの数は異なる場合があります (有向グラフの場合は から の間0、それ以外の場合は と の間)。これが、答えを出すときに と も持つ理由です。もちろん、そう言うことができますが、カジュアルな言い方は です。N^20(N^2)/2NMO(M+N) = O(max(M,N))O(M+N)