Обрезка и поиск

Сокращение и поиск — метод решения задач оптимизации, предложенный Нимродом Мегиддо в 1983 году. ^[1]

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

${\displaystyle T(n)=S(n)+T(n(1-p)).}$

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

В частности, сам Мегиддо использовал этот подход в своем линейном алгоритме времени для задачи линейного программирования , когда размерность фиксирована ^[2] , и для задачи минимальной объемлющей сферы для набора точек в пространстве ^{[1] .}