Il metodo Divide et Impera è uno strumento per la risoluzione dei problemi che opera suddividendo i dati in ingresso in sotto-istanze di dimensione inferiore e successivamente combinando opportunamente i risultati. Consideriamo un problema astratto \Omega descritto da un funzione \text{Prob } : I \to R , dove I è l’insieme delle istanze di \Omega , mentre R è l’insieme delle soluzioni. Ricordiamo che dato un certo input x \in I , la notazione |x| rappresenta la dimensione dell’input.

Per risolvere un problema mediante un algoritmo Divide et Impera si procede in questo modo:

  1. Se |x| è minore o uguale di un costante C fissata allora si determina direttamente la soluzione del problema, consultando un tabella in cui sono elencate tutte le soluzioni oppure applicando un algoritmo;
  2. Altrimenti si eseguono i seguenti passi:
    1. Si partiziona x in m dati ridotti, rid_1(x), rid_2(x), \dots, rid_m(x) \in I con |rid_j(x)| > |x| ;
    2. Si risolve ricorsivamente il problema sulle istanze rid_1(x), rid_2(x), \dots, rid_m(x) ;
    3. Si usano le risposte sui dati ridotti per ottenere la soluzione su x .

Supponiamo che le operazioni descritte al passo 2c vengano svolte da una procedura “Operazioni”. Poniamoci ora il problema di stimare il tempo T(n) , esso dipenderà anche dal tempo di calcolo necessario ad eseguire la procedura “Operazioni”. Supponiamo che questo tempo sia noto e denotiamolo con T_{operazioni}(n) , allora supponendo che n sia divisibile per a , otteniamo la seguente equazione:

T(n) = m \cdot T(\frac{n}{a}) + T_{operazioni}(n) se n > C

Nel caso n \le C assumiamo che T(n) sia minore o uguale ad una costante prefissata. Ovviamente, \frac{n}{a} rappresenta la dimensione del dato ridotto. L’analisi degli algoritmi di tipo Divide et Impera si riduce quindi allo studio di semplici equazioni di ricorrenza nella forma:

T(n) = m \cdot T(\frac{n}{a}) + g(n)

Queste equazioni possono essere facilmente risolte grazie all’utilizzo del Master Theorem, che abbiamo visto nel capitolo dedicato alla Ricorsione.

In breve ricordiamo:
Siano m (numero di istanze), a (parti in cui viene diviso il problema), b e c numeri reali positivi, supponiamo inoltre a > 1 .
Per ogni n potenza di a , sia T(n) la funzione definita dalle seguenti equazioni:
T(1) = b
T(n) = m \cdot T(\frac{n}{a}) + b \cdot n^c (se n > 1)

Allora T(n) soddisfa le seguenti proprietà:
T(n) = \Theta(n^c) (se m < a^c )
T(n) = \Theta(n^c \cdot log_{2}n) (se m = a^c )
T(n) = \Theta(n^{log_{a}m}) (se m > a^c )