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

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

Примеры

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

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

def divide(number: int, divisor: int) -> Tuple[int, int]:
    """Division by subtraction."""
    if divisor == 0:
        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 ( n log h ), работают значительно быстрее для таких наборов точек.

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

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

Обобщения

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

См. также

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