Чувствительный к выходу алгоритм - Output-sensitive algorithm

В Информатика, алгоритм, чувствительный к выходу является алгоритм время выполнения которых зависит от размера вывода, а не от размера ввода или в дополнение к нему. Для некоторых задач, где размер вывода широко варьируется, например от линейного размера ввода до квадратичного размера ввода, анализ, явно учитывающий размер вывода, может дать лучшие границы времени выполнения, которые различают алгоритмы, которые в противном случае одинаковая асимптотическая сложность.

Примеры

Деление на вычитание

Простой пример алгоритма, чувствительного к выходу, дается алгоритм деления деление на вычитание который вычисляет частное и остаток от деления двух положительных целых чисел, используя только сложение, вычитание и сравнения:

def разделять(номер: int, делитель: int) -> Кортеж[int, int]:    "" "Деление на вычитание." ""    если нет делитель:        поднимать ZeroDivisionError    если номер < 1 или же делитель < 1:        поднимать ValueError(            ж«Положительные целые числа только для»            ж"дивиденды ({номер}) и делитель ({делитель})."        )    q = 0    р = номер    пока р >= делитель:        q += 1        р -= делитель    возвращаться q, р

Пример вывода:

>>> разделять(10, 2)(5, 0)>>> разделять(10, 3)(3, 1)

Этот алгоритм занимает Θ (Q) время, и поэтому может быть быстро в сценариях, где известно, что фактор Q невелик. Однако в тех случаях, когда Q велико, оно уступает более сложным алгоритмам, таким как длинное деление.

Вычислительная геометрия

Алгоритмы выпуклой оболочки для поиска выпуклый корпус конечного множества точек на плоскости требуют Ω (п бревно п) время п точки; даже относительно простые алгоритмы, такие как Сканирование Грэма достичь этой нижней границы. Если выпуклая оболочка использует все п очки, это лучшее, что мы можем сделать; однако для многих практических наборов точек и, в частности, для случайных наборов точек, количество точек час в выпуклой оболочке обычно намного меньше, чем п. Следовательно, алгоритмы, чувствительные к выходу, такие как алгоритм конечной выпуклой оболочки и Алгоритм Чана которые требуют только O (п бревно час) время значительно быстрее для таких наборов точек.

Чувствительные к выходу алгоритмы часто возникают в вычислительная геометрия приложений и были описаны для таких проблем, как удаление скрытой поверхности^[1] и решение фильтр диапазона конфликты в таблицах маршрутизатора.^[2]

Франк Нильсен описывает общую парадигму алгоритмов, чувствительных к выходу, известную как группировка и запросы и дает такой алгоритм вычисления ячеек Диаграмма Вороного.^[3] Nielsen разбивает эти алгоритмы на два этапа: оценка выходного размера и последующее построение структур данных на основе этой оценки, которые запрашиваются для построения окончательного решения.

Обобщения

Более общий вид алгоритмов, чувствительных к выходу: алгоритмы перебора, которые перечисляют множество решений проблемы. В этом контексте производительность алгоритмов также измеряется чувствительным к выходу способом в дополнение к более чувствительным мерам, например, ограничению задержки между любыми двумя последовательными решениями.

Смотрите также

Ленивая оценка