Ich teste Sortieralgorithmus und versuchte es mit verschiedenen Datenmengen. 100,000 Elemente 1 Million Elemente bis zu 10 Millionen von Elementen.Wie berechnet man Algorithmuskomplexität durch Laufzeit?
Ich brauche die Komplexität dieses Algorithmus zur Berechnung von Ausgaben für mit, wie lange jede Sortier- nahm.
Wie kann ich das tun?
Während Sie die Laufzeit eines Algorithmus ohne mathematische Analyse nicht finden können, können die empirischen Messungen Ihnen eine vernünftige Vorstellung davon geben, wie sich die Laufzeit des Algorithmus --- oder besser des Programms --- verhält.
Zum Beispiel, wenn Sie n Messungen haben (x1, y1), (x2, y2), ..., (xn, yn), wo xi die Größe des Eingangs und yi ist die Zeit des Programms auf dem Eingang dieser Größe, dann können Sie die Funktion plotten zu sehen, ob es ein Polynom ist. In der Praxis ist es oft so. Es ist jedoch schwer zu sehen, was der Exponent aus der Handlung sein sollte.
die Exponenten finden Sie die Neigung der Linie finden konnten, die am besten (log xi, log yi) die Punkte passen. Dies liegt daran, dass, wenn y=C*x^k+lower order terms, dann, da der Ausdruck C*x^k vorherrscht, wir log y =~ k*log x + log C erwarten, d. H. Die logarithmische Logarithmus-Gleichung ist eine lineare, immer wenn die "ursprüngliche" Gleichung eine polynomische Gleichung ist. (Wenn Sie eine lineare Funktion in der log-log plot sehen, Ihre Laufzeit ist Polynom, die Neigung der Linie sagt Ihnen, den Grad des Polynoms.)
Hier ist eine grafische Darstellung der quadratischen Funktion y(x)=x^2: 
und hier ist das entsprechende log-log Plot: 
Wir können sehen, dass es eine Linie ist mit der Steigung 2 (in der Praxis Sie dies mit berechnen würde, beispielsweise linear least squares). Dies wird erwartet, weil log y(x) = 2 * log(x).
Der Code, den ich verwendet:
x = 1:1:100;
y = x.^2;
plot(x, y);
plot(log(x), log(y));
In der Praxis die Funktion sieht Messier und die Steigung kann (oder sollte) nur als Faustregel verwendet werden, wenn nichts anderes zur Verfügung steht.
Ich stelle mir vor es gibt viele andere Tricks über das Programmverhalten von Laufzeitmessungen zu lernen. Ich gebe anderen eine Chance, ihre Erfahrungen zu teilen.
Sie können nicht wirklich, da die Zeit auch auf der Reihenfolge der Eingabedaten abhängig sein kann. –
Was wäre, wenn ich Schritte hätte, die das Programm benötigt, um die Sortierung jedes Mal abzuschließen? Ich meine "primitive" Schritte. – motleycrue
Es ist immer noch datenabhängig, z.B. Die Blasensortierung reicht von O (n), wenn die Daten nach O (n^2) sortiert sind, wenn die Daten umgekehrt sortiert sind. Sie müssten die Art der Eingabedaten für alle Ihre Testfälle definieren, und selbst dann würde dies nur die Komplexität für diesen speziellen Fall sagen. –