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, del 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 el tamaño de la salida explícitamente pueden producir mejores límites de tiempo de ejecución que diferencian los algoritmos que de otro modo tendrían idéntica complejidad asintótica.
Ejemplos de
División por resta
Un ejemplo simple de un algoritmo sensible a la salida lo da el algoritmo de división división por resta, que calcula el cociente y el resto de dividir dos números enteros positivos usando solo sumas, restas y comparaciones:
def división ( número : int , divisor : int ) -> Tupla [ int , int ]: "" "La división por sustracción" "" si no divisor : aumento ZeroDivisionError si el número < 1 o divisor < 1 : aumento ValueError ( f " Enteros positivos solo para " f " dividendo ( { número } ) y divisor ( { divisor } ). " ) Q = 0 r = número mientras r > = divisor : q + = 1 r - = divisor return q , r
Salida de ejemplo:
>>> dividir ( 10 , 2 ) (5, 0) >>> dividir ( 10 , 3 ) (3, 1)
Este algoritmo toma Θ (Q) tiempo, por lo que 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, los algoritmos más complejos, como la división larga , lo superan .
Geometría Computacional
Los algoritmos de casco convexo para encontrar el casco convexo 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 el casco convexo 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 el casco convexo es típicamente 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 solo requieren 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 conocido como agrupación y consulta y proporciona dicho algoritmo para calcular las 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.
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 una manera sensible a la salida, además de medidas más sensibles, por ejemplo, delimitado el retardo entre dos soluciones sucesivas cualesquiera.
Ver también
Referencias
- ^ Sharir, M .; Overmars, MH (1992). "Un algoritmo sencillo sensible a la salida para la eliminación de superficies ocultas". Transacciones ACM en gráficos . 11 : 1–11. doi : 10.1145 / 102377.112141 . hdl : 1874/16612 .
- ^ Khaireel A. Mohamed y Christine Kupich. Unalgoritmo sensible a la salidaO ( n log n ) para detectar y resolver conflictos para filtros de rango 1D en tablas de enrutadores. Institut für Informatik. 5 de agosto de 2006. ftp://ftp.informatik.uni-freiburg.de/documents/reports/report226/report00226.ps.gz
- ^ Frank Nielsen. Agrupación y consulta: un paradigma para obtener algoritmos sensibles a la salida. Artículos revisados de la Conferencia japonesa sobre geometría discreta y computacional, págs. 250–257. 1998. ISBN 3-540-67181-1 . http://www.sonycsl.co.jp/person/nielsen/PT/groupingquerying/n-grouping.ps