nicht angemeldet
Hallo Peter,
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.
Ja, aber man kann ja maximal so weit schieben, wie das Register breit ist. Also braucht man maximal 64 Schritte, dann ist das Register leer.
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).
Hast Du nicht. Vielleicht weil Dir nicht ganz klar ist, was asymptotische Komplexität oder die O-Notation genau bedeutet.
Angenommen Du hast einen Algorithmus. Der führt irgendwie O(f(n)) Shift-Befehle durch. Ein Shiftbefehl benötigt nun maximal 64 Schritte.
Da 64 * O(f(n)) = O(f(n)) ändert sich am Laufzeitverhalten einfach nix, auch wenn die Befehle bis zu 64 mal so lang brauchen.
Die Argumentation ist einfach, dass sich daraus, ob shift immer 1 Schritt oder bis zu 64 Schritten braucht nur ein Faktor für die Laufzeit ergibt.
So ein Faktor kann natürlich durchaus was ausmachen, schon wenn der Algorithmus nur doppelt so lange braucht, ist das erheblich. Es ist aber oft so, dass man durch einen besseren Algorithmus viel mehr rausholen kann, als dadurch, dass man an irgendwelchen Sachen rumoptimiert, die nur Konstanten beeinflussen.
Grüße
Daniel
Der Martin