Asymptotische Analyse und Vergleich von Sortieralgorithmen
Es ist eine allgemein anerkannte Tatsache, dass die Zusammenführungssortierung schneller abläuft als die Einfügungssortierung. Verwendung der asymptotischen Analyse. Wir können beweisen, dass die Zusammenführungssortierung in O(nlogn) Zeit ausgeführt wird und die Einfügungssortierung O(n^2) benötigt. Dies ist offensichtlich, da die Zusammenführungssortierung einen Divide-and-Conquer-Ansatz verwendet, indem die Probleme rekursiv gelöst werden, während die Einfügungssortierung einem inkrementellen Ansatz folgt. Wenn wir die Zeitkomplexitätsanalyse noch genauer unter die Lupe nehmen, werden wir feststellen, dass die Einfügungssortierung nicht so schlimm genug ist. Überraschenderweise übertrifft die Einfügungssortierung die Zusammenführungssortierung bei kleinerer Eingabegröße. Dies liegt daran, dass es nur wenige Konstanten gibt, die wir bei der Ableitung der Zeitkomplexität ignorieren. Bei größeren Eingabegrößen in der Größenordnung von 10^4 hat dies keinen Einfluss auf das Verhalten unserer Funktion. Wenn die Eingabegrößen jedoch unter, beispielsweise weniger als 40, fallen, dominieren die Konstanten in der Gleichung die Eingabegröße „n“. So weit, ist es gut. Aber ich war mit einer solchen mathematischen Analyse nicht zufrieden. Als Informatikstudent müssen wir an das Schreiben von Code glauben. Ich habe ein C-Programm geschrieben, um ein Gefühl dafür zu bekommen, wie die Algorithmen bei verschiedenen Eingabegrößen miteinander konkurrieren. Und auch, warum eine so strenge mathematische Analyse durchgeführt wird, um die Laufzeitkomplexität dieser Sortieralgorithmen zu ermitteln.
