Loading AI tools
Aus Wikipedia, der freien Enzyklopädie
In der Informatik ist ein ausgabesensitiver Algorithmus ein Algorithmus, dessen Laufzeit von der Größe der Ausgabe abhängt, anstatt oder zusätzlich zur Größe der Eingabe.[1][2]
Ein einfaches Beispiel für einen ausgabesensitiven Algorithmus ist die Division durch Subtraktion, die den Quotienten und den Rest der Division zweier positiver Ganzzahlen berechnet, wobei nur Addition, Subtraktion und Vergleiche verwendet werden:
def divide(p, d: int) -> tuple:
"""Division durch Subtraktion."""
if not d:
raise ZeroDivisionError
if p < 1 or d < 1:
raise ValueError(f'Dividend ({p}) und Divisor ({d})'
' bitte ganzzahlig größer Null.')
q = 0
r = p
while r >= d:
q += 1
r -= d
return q, r
Dieser Algorithmus nimmt Θ(Q) Zeit in Anspruch und kann daher in Szenarien, in denen der Quotient Q bekanntermaßen klein ist, schnell sein. In Fällen, in denen Q groß ist, wird er jedoch von komplexeren Algorithmen wie der schriftlichen Division übertroffen.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.