В информатике чувствительный к выходу алгоритм — это алгоритм , время выполнения которого зависит от размера выходных данных вместо или в дополнение к размеру входных данных. Для некоторых задач, где размер выходных данных сильно варьируется, например, от линейного по размеру входных данных до квадратичного по размеру входных данных, анализы, которые явно учитывают размер выходных данных, могут дать лучшие границы времени выполнения, которые различают алгоритмы, которые в противном случае имели бы одинаковую асимптотическую сложность.
Простой пример алгоритма, чувствительного к выходным данным, — это алгоритм деления через вычитание , который вычисляет частное и остаток от деления двух положительных целых чисел, используя только сложение, вычитание и сравнение:
def divide ( number : int , divisor : int ) -> Tuple [ int , int ]: """Деление вычитанием.""" if divisor == 0 : raise ZeroDivisionError if number < 1 or divisor < 1 : raise ValueError ( f "Положительные целые числа только для " f "dividend ( { number } ) и divisor ( { divisor } )." ) q = 0 r = number while r >= divisor : q += 1 r -= divisor return q , r Пример вывода:
>>> разделить ( 10 , 2 ) (5, 0) >>> разделить ( 10 , 3 ) (3, 1)Этот алгоритм занимает Θ (Q) времени и поэтому может быть быстрым в сценариях, где известно, что частное Q мало. Однако в случаях, когда Q велико, он уступает более сложным алгоритмам, таким как длинное деление .
Алгоритмы выпуклой оболочки для нахождения выпуклой оболочки конечного набора точек на плоскости требуют Ω( n log n ) времени для n точек; даже относительно простые алгоритмы, такие как сканирование Грэма, достигают этой нижней границы. Если выпуклая оболочка использует все n точек, это лучшее, что мы можем сделать; однако для многих практических наборов точек, и в частности для случайных наборов точек, количество точек h в выпуклой оболочке обычно намного меньше n . Следовательно, алгоритмы, чувствительные к выходным данным, такие как алгоритм конечной выпуклой оболочки и алгоритм Чана , которые требуют только O( n log h ) времени, значительно быстрее для таких наборов точек.
Алгоритмы, чувствительные к выходным данным, часто возникают в приложениях вычислительной геометрии и были описаны для таких задач, как удаление скрытых поверхностей [1] и разрешение конфликтов фильтра диапазона в таблицах маршрутизаторов. [2]
Фрэнк Нильсен описывает общую парадигму алгоритмов, чувствительных к выходным данным, известную как группировка и запросы , и приводит такой алгоритм для вычисления ячеек диаграммы Вороного . [3] Нильсен разбивает эти алгоритмы на два этапа: оценка размера выходных данных и последующее построение структур данных на основе этой оценки, которые запрашиваются для построения окончательного решения.
Более общим видом выходно-чувствительных алгоритмов являются алгоритмы перечисления , которые перечисляют множество решений проблемы. В этом контексте производительность алгоритмов также измеряется выходно-чувствительным способом, в дополнение к более чувствительным мерам, например, ограничению задержки между любыми двумя последовательными решениями.