En ciencias de la computación, un algoritmo sensible a la salida es un tipo de algoritmo cuyo tiempo de ejecución depende del tamaño de la salida, en lugar de, o además de, el tamaño de la entrada. Para ciertos problemas donde el tamaño de la salida varía ampliamente, por ejemplo, de lineal a cuadráticamente con respecto al tamaño de la entrada, los análisis que consideran explícitamente el tamaño de la salida pueden producir mejores límites de tiempo de ejecución que diferencian algoritmos que, de otro modo, tendrían una complejidad asintótica idéntica.
Ejemplos
División por resta Un ejemplo sencillo de un algoritmo sensible a la salida es el algoritmo de división mediante división por resta, que calcula el cociente y el resto de la división de dos enteros positivos utilizando únicamente suma, resta y comparaciones:
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
Ejemplo de salida: >>> divide(10, 2) (5, 0) >>> divide(10, 3) (3, 1)
Este algoritmo requiere un tiempo Θ(Q), por lo que puede ser rápido en escenarios donde se sabe que el cociente Q es pequeño. Sin embargo, en casos donde Q es grande, algoritmos más complejos como la división larga lo superan en rendimiento.
Geometría computacional Los algoritmos de envolvente convexa, para encontrar el contorno de un conjunto finito de puntos en el plano, requiere un tiempo Ω(n log n) para n puntos. Incluso algoritmos relativamente simples como el método de Graham alcanzan este límite inferior. Si la envolvente convexa utiliza los n puntos, este es el mejor resultado posible; sin embargo, para muchos conjuntos de puntos prácticos, y en particular para conjuntos aleatorios, el número de puntos h en la envolvente convexa suele ser mucho menor que n. En consecuencia, algoritmos sensibles a la salida, como el algoritmo definitivo de envolvente convexa y el algoritmo de Chan, que requieren solo un tiempo O(n log h), son considerablemente más rápidos para dichos conjuntos de puntos.
Los algoritmos sensibles a la salida surgen con frecuencia en aplicaciones de geometría computacional y se han descrito para problemas como la determinación de cara oculta y la resolución de conflictos de rango de filtrado en tablas de enrutamiento.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
Frank Nielsen describe un paradigma general de algoritmos sensibles a la salida conocido como agrupación y consulta y proporciona un algoritmo para calcular celdas de los polígonos de Thiessen.Frank Nielsen. Grouping and Querying: A Paradigm to Get Output-Sensitive Algorithms. Revised Papers from the Japanese Conference on Discrete and Computational Geometry, pp.250–257. 1998. . http://www.sonycsl.co.jp/person/nielsen/PT/groupingquerying/n-grouping.ps Nielsen divide estos algoritmos en dos etapas: estimar el tamaño de la salida y, a continuación, construir estructuras de datos basadas en dicha estimación, las cuales se consultan para construir la solución final.
Generalizaciones Un tipo más general de algoritmos sensibles a la salida son los algoritmos de enumeración, que enumeran el conjunto de soluciones a un problema. En este contexto, el rendimiento de los algoritmos también se mide de forma sensible a la salida, además de otras medidas más sensibles, como el retardo entre dos soluciones sucesivas.
Véase también Evaluación perezosa
Referencias
Categoría:Análisis de algoritmos