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.
Beispiele Division durch Subtraktion 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.
Siehe auch Landau-Symbole Gift-Wrapping-Algorithmus
Einzelnachweise
Kategorie:Algorithmus