java- Big O Notation - Unterschied zwischen MlogN und MlogM?

Question

Wenn ich den dominanten Begriff von M log (N) + M log (M) finden wollte, was soll ich tun? Was ist der Unterschied zwischen MlogN und MlogM ???

Answer 1

Welche davon dominant ist, hängt davon ab, ob M > N oder M < N. Wenn M > N, Mlog(N) < M log(M). Wenn M < N, dann M log(N) > M log(M). Eine vollständige Analyse:

• Halten M konstant ist und so dass N variieren, ist dieser O(log(N))
• Halten N konstant und damit M variieren, ist dies O(M log(M))
• Zulassen von sowohl N als auch M zu variieren, das ist O(M log(N) + M log(M)) = O(M(log(N) + log(M)) = O(M log(MN)).

Fragen Sie sich, ob Sie zu einem bestimmten Fall oder Klasse von Eingaben werden, wo eine bestimmte Beziehung zwischen M und N, und wenn ja, verwenden Sie diese Beziehung abzuleiten Ihre Antwort. Ansonsten gibt es im Allgemeinen keinen einzelnen "dominanten" Ausdruck, da der dominierende Anteil von der Beziehung zwischen N und M abhängt.

Das heißt - steigende M allein erhöht den Wert des Ausdrucks schneller als N allein erhöhen, wenn Sie wie Erhöhungen vergleichen.