Ausgabesensitiver Algorithmus

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen

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]

Division durch Subtraktion

[Bearbeiten | Quelltext bearbeiten]

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.

Einzelnachweise

[Bearbeiten | Quelltext bearbeiten]
  1. Volker Turau: Algorithmische Graphentheorie. Oldenbourg Verlag, 2010, ISBN 978-3-486-59852-0 (google.com [abgerufen am 10. Mai 2020]).
  2. SharirMicha, OvermarsMark H: A simple output-sensitive algorithm for hidden surface removal. In: ACM Transactions on Graphics (TOG). 2. Januar 1992, doi:10.1145/102377.112141 (acm.org [abgerufen am 10. Mai 2020]).