Unterscheidung der Komplexität von zwei Algorithmen

Hallo zusammen,

das Informatik-Forum geht in den Archivmodus, genaue Informationen kann man der entsprechenden Ankündigung entnehmen. Als Dankeschön für die Treue bekommt man von uns einen Gutscheincode (informatikforum30) womit man bei netzliving.de 30% auf das erste Jahr sparen kann. (Genaue Infos sind ebenfalls in der Ankündigung)

Vielen Dank für die Treue und das Verständnis!

    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...

    Der Faktor 3 ist nur eine Beobachtung, könnte auf anderer Hardware, mit anderem Compiler,... anders aussehen.
    Die Komplexität ist interessanter und auch eindeutig zu bestimmen. Dabei geht es nur um die Größenordnung, welche hier gleich ist. Der Faktor ist egal.

    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?