nicht angemeldet
Hallo Daniel,
Wieso nun das? Martin schrieb: "Bei der klassischen Intel-Architektur ist aber der Zeitaufwand für eine Schiebeoperation tatsächlich proportional zur Anzahl der Bitpositionen."
Das ist schon richtig. Da ein Prozessor aber nur mit einigen wenigen (im Vergleich zur Unendlichkeit ;) Bits, z.Z. meist 32 oder 64 arbeitet, sind das eben konstant viele Schritte. Also eben O(64) = O(1).
Das hieße, der Zeitaufwand für die Schiebeoperation ist proportional zur Registerbreite. Ich hab Martin aber so verstanden, dass der Aufwand proportional zum Abstand ist, um den man verschieben möchte.
Daraus ergibt sich dann, dass das Laufzeitverhalten des Shiftbefehls selbst sich nicht auf das asymptotische Laufzeitverhalten Deines Algorithmuses auswirken kann. Das Verhalten muss sich schon aus diesem selbst ergeben.
Du meinst also, es dauert genauso lang, Millionen von "foo << 1" durchzuführen wie "foo << 12"? Andernfalls kann das ja eine Auswirkung haben (oder ich habe deine Argumentation nicht verstanden).
Bye,
Peter
Der Martin