nicht angemeldet
Hallo Peter,
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 kann natürlich bedeuten, dass Dein Programm 64 mal so lang braucht als es auf einem Prozessor brauchen würde, der das in einem Schritt kann. Für die asymptotische Laufzeit macht das aber erstmal keinen unterschied.
Nun kann man natürlich sagen, dass alle direkt unterstützten Datentypen irgendwie beschränkt sind und damit auch das durchlaufen eines integer-indizierten Arrays in konstanter Zeit geht. Der unterschied ist, dass die maximale Shift-weite eben sehr klein ist, ein maximaler Integer Wert aber so groß, dass man ihn für die Analyse von Algorithmen meist als uneingeschränkt betrachten kann/muss.
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. Es kann ja sein, dass 64 Bit viel zu wenig sind und Du irgendwie mit 1MBit-Vektoren arbeiten musst. Da ist natürlich ein Shift wirklich aufwendig. Nur macht den auch nicht mehr der Prozessor für Dich.
Grüße
Daniel
Der Martin