Bitweiser Zugriff

[Daniel Thoma]

Hallo Peter,

Da ist schon der Haken, ich habe doch nie von einem Algorithmus mit O(f(n)) gesprochen. Als Gegenbeispiel stelle man sich einen Algorithmus vor, dem man ein Array der Länge n und einen Parameter b übergibt. Der Algorithmus soll die Bits aller Arrayelemente um b Positionen verschieben. Ich behaupte nun, die Komplexität ist in diesem Fall O(b * n) gilt, denn b ist ja variabel. Siehst du das nicht auch so?

Sicher, nur hängt das nicht davon ab, wie schnell der Shift-Befehl des Prozessors ist.
Vergleichen wir beide Fälle:
1. Du implementierst diesen Algorithmus mit einem Shift-Befehl, der immer in einem Schritt durchkommt (vermutlich geht besser als logarithmisch nicht, aber nehmen wir das der Einfachheit halber mal an)
Du musst maximal für jedes Element um 63 Bit shiften (wenn man 64 Bit/Element annimmt). Wenn b > 63 ist, dann musst Du die Elemente im Array vertauschen und nur noch b % 64 Bits shiften, also der Anteil, der eben nicht aufgeht.
Das verschieben der Elemente geht wohl in O(n), indem man einfach ein Element an den Platz abrunden(b / 64) setzt. Du kommst also tatsächlich mit O(n) Schritten aus.

2. Du implementierst den Algorithmus mit einem Shift-Befehl, der so viel Schritte braucht, wie geshiftet wird.
Nun es ändert sich nicht viel, außer dass Du für jedes Element bis zu 63 Schritte zum Shiften brauchst.
Statt O(n) Schritten brauchst Du eben 63 * O(n) Schritte. Das ist per Definition eben ebenfalls O(n).

Ich weiß nicht mehr so recht, wie ich es noch genauer ausführen soll ;-)

Meine Aussage ist ja nur, dass das asymptotische Verhalten nicht von der Art des Shift-Befehls auf Prozessorebene abhängt.
Natürlich braucht der Shift für ein beliebig großes Array O(n) Schritte. Natürlich wird es auch schneller, wenn der shift im Prozessor schneller arbeitet. Es bringt aber nichts darüber nachzudenken, wie schnell der Prozessor shiftet, wenn der Algorithmus zum shiften des großen Arrays z.B. so schlecht wäre, dass er ohnehin O(n²) Schritte bräuchte.
Mehr als: "Wenn man Anfängt über Prozessorbefehle nachzudenken, sollte man erstmal einen Schritt zurücktreten und gucken, ob es nicht irgendwie alles viel einfacher geht" wollte ich im Grunde nicht sagen ;-)

Grüße

Daniel