Im Buch Einführung in Algorithmen (Corman) stellt Übung 1.2-2 die folgende Frage zum Vergleich von Implementierungen von Einfügesortierung und Zusammenführungssortierung. Bei Eingaben der Größe n wird die Einfügesortierung in 8n ^ 2 Schritten ausgeführt, während die Zusammenführungssortierung in 64n lg n Schritten ausgeführt wird. für welche Werte von n tut Insertion sort beat merge sort?
Obwohl ich an der Antwort interessiert bin, interessiere ich mich mehr dafür, wie ich die Antwort Schritt für Schritt finde (so dass ich den Prozess wiederholen kann, um irgendwelche zwei gegebenen Algorithmen wenn überhaupt zu vergleichen).
Auf den ersten Blick scheint dieses Problem ähnlich zu sein, wie den Break-Even-Punkt in der Business-Analysis zu finden, eine Klasse, die ich vor mehr als fünf Jahren gemacht habe, aber ich bin mir nicht sicher, dass jede Hilfe geschätzt würde.
Danke
P / S Wenn meine Tags falsch sind, diese Frage falsch kategorisiert ist oder eine andere Konvention hier missbraucht wird, beschränken Sie bitte die Beschimpfung auf ein Minimum, da dies das erste Mal ist, dass ich eine Frage posten muss.
Tags und Links algorithm mergesort time-complexity sorting insertion-sort