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

Einzelnachweise

  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]).
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.