Ausgabesensitiver Algorithmus

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