Laufzeit von Addition von 2 Zahlen |
| 21.01.2010, 14:14 | DarkBullet | Auf diesen Beitrag antworten » | ||
| Laufzeit von Addition von 2 Zahlen ich habe eine Frage aus der Informatik bei der ich mir überhaupt nicht sicher bin. Und zwar wie der Aufwand der Addition von 2 Zahlen (32-bit float, 64-bit double, ...) ausschaut. Es müsste doch immer O(1) sein, aber irgendwie ist unser Prof. noch auf O(n*log(n)) gekommen (ich glaube es es jetzt n*log(n) war), jedenfalls müsste es doch immer O(1) betragen 2 Zahlen zu addieren und sonst nichts, oder? Hoffe mir kann wer helfen. Danke |
||||
| 23.01.2010, 00:36 | Abakus | Auf diesen Beitrag antworten » | ||
RE: Laufzeit von Addition von 2 Zahlen
Hallo! Ja, denke ich auch. Vermutlich liegt da eine Verwechselung mit dem Sortieren von n Zahlen via Quicksort oder so vor. Ansonsten ist ungeklärt, was n hier sein soll. Grüße Abakus 
|
||||
| 23.01.2010, 12:52 | Mystic | Auf diesen Beitrag antworten » | ||
| RE: Laufzeit von Addition von 2 Zahlen Wenn n eine Obergrenze für die Anzahl der Binärziffern der beiden zu addierenden Zahlen darstellt, dann sollte rein theoretisch der Aufwand für die Addition O(n) sein... Für großes n stimmt das auch sicher so, für kleines n (also wenn n z.B. höchstens 32 bzw. 64 ist, je nach Prozessortyp) wird das aber u.U. dadurch verfälscht, dass dann "prozessorintern" fix verdrahtete Routinen ablaufen, wo die "wahre Stelligkeit" der involvierten Zahlen dann möglicherweise egal ist... |
||||
| 23.01.2010, 13:10 | kiste | Auf diesen Beitrag antworten » | ||
RE: Laufzeit von Addition von 2 Zahlen
Quicksort ist nur im Average Case n*log(n). Im Worst-Case ist es ein quadratischer Algorithmus. Das Addieren zweier n-Bit Zahlen funktioniert natürlich nicht in konstanter Zeit. Sehe allerdings auch nicht wie man auf n*log(n) kommen sollte. Denke auch das es maximal O(n) ist. |
||||
|
|
Verwandte Themen
| Die Beliebtesten » |
| Die Größten » |
|
| Die Neuesten » |
|
