Hallo Forum!
Ich habe die Laufzeiten zweier Algorithmen in Abhängigkeit von der Eingabegröße gemessen und die Messwerte anschließend in einem Diagramm abgetragen (und jeweils eine Kurve generiert).
Die Kurve von Algorithmus 1 wächst steiler als von Algorithmus 2 (beide Algorithmen haben eine kubische Komplexität).

Beim Ausrechnen der Komplexität gibt es ja einen konstanten Faktor c, der hardwarespezifisch ist. Je nach Prozessor kann ein Algorithmus ja schneller oder langsamer laufen und das c kann somit kleiner oder größer sein.
Algorithmus 1 und 2 wurden jeweils unter selben Bedinungen gemessen. Der hardwarespezifische Faktor c müsste also bei beiden gleich sein. Da Algorithmus 1 jedoch schneller wächst (meinetwegen 3n^3) als Algorithmus 1(z.B. 1n^3), kann man doch behaupten, dass die Komplexität von Algorithmus 1 größer ist als von Algorithmus 2, oder? Ich habe bis jetzt immer nur gesehen, dass die Komplexität durch den Exponenten festgelegt wird. Dann wäre sie ja bei beiden Algorithmen gleich...

Okay, bei den Messungen mag das vllt. nicht funktionieren.
Ich habe durch Berechnungen folgendes festgestellt:

Sei B als Blockgröße definiert. (Größe einer Speicherzelle).

Es werden genau (1/B) * N^3 Operationen ausgeführt.

Die Laufzeit hat also die Komplexität von:

c * (1/B) * N^3

Nun bringe ich 1/B einfach in den Exponenten.
1/B = N^(log von 1/B zur Basis N)

Einsetzen:

c * N^(log von 1/B zur Basis N) * N^3

Zusammenfassen:

c * N^(3 + log von 1/B zur Basis N)

EDIT: Vereinfacht: c * N^(3 - log von B zur Basis N)

Leider weiß ich nicht ganz wie ich das N aus dem exponenten bekomme aber damit kann ich doch zeigen, dass für große Blockgrößen (z.B. 64 Bit) die Komplexität verringert werden kann(denn die Ordnung verringert sich ja), oder?

Beispielrechnung für N = 800

Ohne Faktor (1/B): N^3

Mit Faktor (1/B): N^2,48

Wenn ich also nachweisen möchte, dass die Komplexität durch einen Faktor gesenkt wird, sollte ich dann diesen Faktor einfach in den Exponenten bringen um so den Unterschied in der Ordnung nachzuweisen, statt den Faktor vor das N zu schreiben?