java-Big O表記 - MlogNとMlogMの違いは？

Question

私がM log (N) + M log (M)の支配的な用語を探したければ、どうすればよいですか？ MlogNとMlogMの違いは何ですか？

Answer 1

どちらが優位であるかは、M > NまたはM < Nのいずれであるかによって異なります。 M > N,Mlog(N) < M log(M)。 M < Nの場合は、M log(N) > M log(M)です。完全分析：これは、O(log(N))

ホールディングN定数及びMを変化させる

• ホールディングM定数とNを変化させることであり、これはNとMの両方が変化することが許可O(M log(M))
• あり、これはO(M log(N) + M log(M)) = O(M(log(N) + log(M)) = O(M log(MN))。

あなたはMとNの間に明確な関係があるの入力の特定の場合またはクラスを見ているかどうかを自問して、もしそうなら、あなたの答えを導き出すためにその関係を使用しています。それ以外の場合、一般的には、支配的なものはNとMの関係に依存するため、単一の「支配的」という用語はありません。

あなたが増加のようなものを比較している場合、Mだけを増やすだけでは、Nだけを増やすよりも速く表現の価値が上がります。