Output-sensitive algorithm
In computer science, an output-sensitive algorithm is an algorithm whose running time depends on the size of the output, instead of, or in addition to, the size of the input. For certain problems where the output size varies widely, for example from linear in the size of the input to quadratic in the size of the input, analyses that take the output size explicitly into account can produce better runtime bounds that differentiate algorithms that would otherwise have identical asymptotic complexity.
Examples
Division by subtraction
A simple example of an output-sensitive algorithm is given by the division algorithm division by subtraction which computes the quotient and remainder of dividing two positive integers using only addition, subtraction, and comparisons:
def divide(number: int, divisor: int) -> Tuple[int, int]:
"""Division by subtraction."""
if divisor == 0:
raise ZeroDivisionError
if number < 1 or divisor < 1:
raise ValueError(
f"Positive integers only for "
f"dividend ({number}) and divisor ({divisor})."
)
q = 0
r = number
while r >= divisor:
q += 1
r -= divisor
return q, r
Example output:
>>> divide(10, 2)
(5, 0)
>>> divide(10, 3)
(3, 1)
This algorithm takes Θ(Q) time, and so can be fast in scenarios where the quotient Q is known to be small. In cases where Q is large however, it is outperformed by more complex algorithms such as long division.
Computational geometry
Output-sensitive algorithms arise frequently in
Frank Nielsen describes a general paradigm of output-sensitive algorithms known as grouping and querying and gives such an algorithm for computing cells of a Voronoi diagram.[3] Nielsen breaks these algorithms into two stages: estimating the output size, and then building data structures based on that estimate which are queried to construct the final solution.
Generalizations
A more general kind of output-sensitive algorithms are enumeration algorithms, which enumerate the set of solutions to a problem. In this context, the performance of algorithms is also measured in an output-sensitive way, in addition to more sensitive measures, e.g., bounded the delay between any two successive solutions.
See also
References
- hdl:1874/16612.
- ^ Khaireel A. Mohamed and Christine Kupich. An O(n log n) Output-Sensitive Algorithm to Detect and Resolve Conflicts for 1D Range Filters in Router Tables. Institut für Informatik. August 5, 2006. ftp://ftp.informatik.uni-freiburg.de/documents/reports/report226/report00226.ps.gz