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 de, o además de, el tamaño de la entrada. Para ciertos problemas en los que el tamaño de la salida varía ampliamente, por ejemplo, de lineal en el tamaño de la entrada a 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 una complejidad asintótica idéntica.
Un ejemplo simple de un algoritmo sensible a la salida lo da el algoritmo de división por resta, que calcula el cociente y el resto de dividir dos números enteros positivos utilizando únicamente suma, resta y comparaciones:
def divide ( numero : int , divisor : int ) -> Tupla [ int , int ]: """División por resta.""" if divisor == 0 : raise ZeroDivisionError if number < 1 or divisor < 1 : raise ValueError ( f "Solo números enteros positivos para " f "dividendo ( { number } ) y divisor ( { divisor } )." ) q = 0 r = number while r >= divisor : q += 1 r -= divisor return q , r Ejemplo de salida:
>>> dividir ( 10 , 2 ) (5, 0) >>> dividir ( 10 , 3 ) (3, 1)Este algoritmo requiere un tiempo Θ (Q), por lo que puede ser rápido en situaciones en las que se sabe que el cociente Q es pequeño. Sin embargo, en los casos en los que Q es grande, su rendimiento es superado por algoritmos más complejos, como la división larga .
Los algoritmos de envoltura convexa para encontrar la envoltura convexa de un conjunto finito de puntos en el plano requieren un tiempo Ω( n log n ) para n puntos; incluso algoritmos relativamente simples como el escaneo de Graham logran este límite inferior. Si la envoltura convexa usa todos 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 la envoltura convexa es típicamente mucho menor que n . En consecuencia, los algoritmos sensibles a la salida como el algoritmo de envoltura convexa definitiva y el algoritmo de Chan que requieren solo un 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 agrupamiento 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 con medidas más sensibles, por ejemplo, acotando el retraso entre dos soluciones sucesivas.