Output sensitive algorithm

This article was due to content flaws on the quality assurance side of the computer science editorial added. This is done in order to bring the quality of the articles from the subject area of ​​computer science to an acceptable level. Help to eliminate the shortcomings in this article and take part in the discussion !  ( + )

In computer science, an output-sensitive algorithm is an algorithm whose runtime depends on the size of the output instead of or in addition to the size of the input.

Examples

Division by subtraction

A simple example of an output-sensitive algorithm is division by subtraction , which calculates the quotient and the remainder of the division of two positive integers, using only addition, subtraction, and comparisons:

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

This algorithm takes Θ (Q) time and can therefore be fast in scenarios in which the quotient Q is known to be small. However, in cases where Q is large, it is outperformed by more complex algorithms such as written division .

See also

• Landau symbols
• Poison wrapping algorithm

Individual evidence

1. ↑ Volker Turau: Algorithmic Graph Theory . Oldenbourg Verlag, 2010, ISBN 978-3-486-59852-0 ( google.com [accessed May 10, 2020]).
2. ↑ SharirMicha, OvermarsMark H: A simple output-sensitive algorithm for hidden surface removal . In: ACM Transactions on Graphics (TOG) . January 2, 1992, doi : 10.1145 / 102377.112141 ( acm.org [accessed May 10, 2020]).