Prune and search

Prune and search (in italiano "sfoltisci e cerca") è un metodo per risolvere problemi di ottimizzazione ideato da Nimrod Megiddo nel 1983.^[1]

L'idea alla base del metodo è una procedura ricorsiva, ad ogni passo della quale la taglia dell'input è ridotta (prune) di un fattore costante ${\displaystyle 0<p<1}$. Esso è dunque un algoritmo del tipo divide et impera. Sia ${\displaystyle n}$ la taglia dell'input, ${\displaystyle T(n)}$ sarà la complessità temporale di tutto l'algoritmo e ${\displaystyle S(n)}$ la complessità temporale dell'operazione di sfoltimento, allora ${\displaystyle T(n)}$ obbedirà alla seguente relazione di ricorrenza:

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

che si può provare, col metodo di Akra-Bazzi, avere soluzione ${\displaystyle T(n)=O(1+\int _{1}^{x}{\frac {S(u)}{u}}du)}$, se ${\displaystyle |S'(n)|=O(x^{c})}$, dove c è una costante.