Wikipedia listet die zeitliche Komplexität der Addition als , wobei die Anzahl der Bits ist.
Ist das eine starre theoretische Untergrenze? Oder ist dies nur die Komplexität des derzeit schnellsten bekannten Algorithmus? Ich möchte wissen, weil die Komplexität der Addition alle anderen arithmetischen Operationen und alle Algorithmen, die sie verwenden, unterstreicht.
Ist es theoretisch unmöglich, einen Additionsalgorithmus zu erhalten, der in läuft ? Oder sind wir zur Addition an lineare Komplexität gebunden?
quelle
Damit die Komplexitätsanalyse überhaupt einen formalen Sinn ergibt, müssen Sie ein formales Rechenmodell angeben, in dem der Algorithmus im Objekt ausgeführt wird, oder zumindest ein Kostenmodell , das die grundlegenden Operationen und festlegt ihre Kosten.
In den meisten Kontexten wird angenommen, dass arithmetische Operationen Zeit benötigen . Dies ist normalerweise sinnvoll, da wir an der algorithmischen Komplexität unabhängig von den beteiligten Zahlen interessiert sind. Dies wird als einheitliches Kostenmodell bezeichnet .Θ(1)
Wenn Zahlen unbegrenzt wachsen können oder wir daran interessiert sind, die Operationen selbst zu analysieren, wird angenommen, dass arithmetische Operationen Kosten , die proportional zur Größe der Eingabe sind.Θ(|x|)
Können Operationen Kosten verursachen, die geringer sind? Möglicherweise müssen Sie jedoch ein Rechenmodell formal definieren, in dem dies geschehen kann.
quelle
Die Eingabe zur Addition besteht aus zwei beliebigen Zahlen. Da sie beliebig sind, müssen Sie jedes Bit lesen, und daher ist der Algorithmus .Ω(n)
Stellen Sie sich vor, Ihr Algorithmus fügt erfolgreich 1010100110 und 0010010110 hinzu, ohne jedes Bit zu lesen. Damit Ihr Algorithmus beliebige Eingaben hinzufügen kann, sollte ich in der Lage sein, eines dieser Bits zufällig umzudrehen, und der Algorithmus gibt immer noch eine korrekte (aber unterschiedliche) Addition aus. Aber wenn Ihr Algorithmus nicht jedes Bit liest, wie kann er dann feststellen, dass sich die gespiegelte Eingabe von der ursprünglichen Eingabe unterscheidet?
quelle