En informática , un algoritmo sensible a la salida es un algoritmo cuyo tiempo de ejecución depende del tamaño de la salida, en lugar o además del tamaño de la entrada. Para ciertos problemas en los que el tamaño de salida varía ampliamente, por ejemplo, desde lineal en el tamaño de la entrada hasta cuadrático en el tamaño de la entrada, los análisis que tienen en cuenta 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 idéntica complejidad asintótica.
Un ejemplo simple de un algoritmo sensible a la salida lo brinda el algoritmo de división división por resta que calcula el cociente y el resto de la división de dos enteros positivos usando solo suma, resta y comparaciones:
def dividir ( número : int , divisor : int ) -> Tupla [ int , int ]: """División por resta.""" si divisor == 0 : generar ZeroDivisionError si número < 1 o divisor < 1 : generar ValueError ( f " Enteros positivos sólo para " f "dividendo ( { número } ) y divisor ( { divisor } ) q = 0 r = número mientras r >= divisor : q += 1 r -= divisor devuelve q , r Salida de ejemplo:
>>> dividir ( 10 , 2 ) (5, 0) >>> dividir ( 10 , 3 ) (3, 1)Este algoritmo requiere Θ (Q) tiempo y, por lo tanto, puede ser rápido en escenarios donde se sabe que el cociente Q es pequeño. Sin embargo, en los casos en los que Q es grande, es superado por algoritmos más complejos, como la división larga .
Los algoritmos de casco convexo para encontrar el casco convexo de un conjunto finito de puntos en el plano requieren Ω( n log n ) tiempo para n puntos; Incluso algoritmos relativamente simples como el escaneo de Graham logran este límite inferior. Si el casco convexo utiliza los n puntos, esto es lo mejor que podemos hacer; sin embargo, para muchos conjuntos prácticos de puntos, y en particular para conjuntos aleatorios de puntos, el número de puntos h en el casco convexo suele ser mucho menor que n . En consecuencia, los algoritmos sensibles a la salida, como el algoritmo de casco convexo definitivo y el algoritmo de Chan , que requieren sólo tiempo O ( n log h ), son considerablemente más rápidos para tales 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 eliminación de superficies ocultas [1] y la resolución de conflictos de filtros de rango en tablas de enrutadores. [2]
Frank Nielsen describe un paradigma general de algoritmos sensibles a la salida conocidos como agrupación y consulta y proporciona dicho algoritmo para calcular celdas de un diagrama de Voronoi . [3] Nielsen divide estos algoritmos en dos etapas: estimar el tamaño de salida y luego construir estructuras de datos basadas en esa estimación que se consultan para construir la solución final.
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 medidas más sensibles, por ejemplo, limitando el retraso entre dos soluciones sucesivas.