Обрезать и искать

«Отсечение и поиск» — метод решения задач оптимизации, предложенный Нимродом Мегиддо в 1983 году.

Основная идея метода — рекурсивная процедура, в которой на каждом шаге размер входных данных уменьшается («обрезается») на постоянный коэффициент 0 < p < 1 . По существу, это форма алгоритма уменьшения и завоевания , где на каждом шаге уменьшение происходит на постоянный коэффициент. Пусть n будет входным размером, T ( n ) будет временной сложностью всего алгоритма сокращения и поиска, а S ( n ) будет временной сложностью шага сокращения. Тогда T ( n ) подчиняется следующему рекуррентному соотношению :

$T(n)=S(n)+T(n(1-p)).$

Это похоже на повторение двоичного поиска , но имеет больший член S ( n ), чем постоянный член двоичного поиска. В алгоритмах сокращения и поиска S(n) обычно является как минимум линейным (поскольку необходимо обработать весь ввод). При этом предположении рекуррентность имеет решение T ( n ) = O ( S ( n )) . В этом можно убедиться либо применив основную теорему для повторений по принципу «разделяй и властвуй», либо наблюдая, что время решения рекурсивных подзадач уменьшается в геометрической прогрессии .

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