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

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

Примеры

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

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

def divide(number: int, divisor: int) -> Tuple[int, int]:
    """Division by subtraction."""
    if not divisor:
        raise ZeroDivisionError
    if number < 1 or divisor < 1:
        raise ValueError(
            f"Positive integers only for "
            f"dividend ({number}) and divisor ({divisor})."
        )
    q = 0
    r = number
    while r >= divisor:
        q += 1
        r -= divisor
    return q, r

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

>>> divide(10, 2)
(5, 0)
>>> divide(10, 3)
(3, 1)

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

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

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

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

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

Обобщения

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

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

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

Рекомендации