Mathematik online lernen im Mathe-Forum. Nachhilfe online
Startseite » Forum » Binäre Zahlen, Laufzeit

Binäre Zahlen, Laufzeit

Universität / Fachhochschule

Tags: Division

 
Antworten Neue Frage stellen Im Forum suchen
Neue Frage
anonymous

anonymous

14:25 Uhr, 10.10.2019

Antworten
Hallo,
es sei a eine binäre Zahl mit der Länge m und b eine binäre Zahl mit der Länge n.
Nun soll a mit Rest durch b dividiert werden.
Bei der Analyse dieses Algorithmus stellt man fest:
Wenn k die Anzahl der Bits des Quotient darstellt, dann muss man höchstens k mal 2 Zahlen mit der Länge =< n+1 abziehen. --> Das kostet Zeit O(kn).

Warum ist die Länger immer kleiner gleich n+1?


Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert):
"Ich benötige bitte nur das Ergebnis und keinen längeren Lösungsweg."
Hierzu passend bei OnlineMathe:

Online-Übungen (Übungsaufgaben) bei unterricht.de:
 
Online-Nachhilfe in Mathematik
Antwort
ledum

ledum aktiv_icon

15:18 Uhr, 10.10.2019

Antworten
Hallo
man muss doch höchstens b selbst bzw b-1 abziehen, und die Länge ist immer <n+1 also höchstens n
Gruß ledum
anonymous

anonymous

10:18 Uhr, 04.11.2019

Antworten
Was soll man wovon abziehen? und warum?
Diese Frage wurde automatisch geschlossen, da der Fragesteller kein Interesse mehr an der Frage gezeigt hat.