Prune and search

Questa voce sugli argomenti informatica e matematica è solo un abbozzo.

Contribuisci a migliorarla secondo le convenzioni di Wikipedia. Segui i suggerimenti dei progetti di riferimento 1, 2.

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.